Hadwiger Number

Author

Eric W. Weisstein
May 15, 2023

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/HadwigerNumber.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/HadwigerNumber.html.

©2023 Wolfram Research, Inc. except for portions noted otherwise

Missing

missing=Select[GraphData[All],MissingQ[GraphData[#,"HadwigerNumber"]]&];

Grid[Take[gm=DeleteCases[Sort[GraphData[#,{"MinorCount","V","#"}]&/@missing],{_Missing,_,_}],UpTo[20]],Dividers->All,Alignment->{{{Decimal},Left},Automatic}]

gm[[All,-1]]

Hadwiger conjecture

https://en.wikipedia.org/wiki/Hadwiger_number

The Hadwiger conjecture states that the Hadwiger number is always at least as large as the chromatic number of G. That is, every graph with Hadwiger number k should have a graph coloring with at most k colors. The case k = 4 is equivalent (by Wagner's characterization of the graphs with this Hadwiger number) to the four color theorem on colorings of planar graphs, and the conjecture has also been proven for k ≤ 5, but remains unproven for larger values of k.

Cases[{#,#2,#3,#2≤#3}&@@@(GraphData[#,{"#","ChromaticNumber","HadwigerNumber"}]&/@GraphData[All]),{_,_,_,False}]

By integer

1

empty graphs

2

A graph G has Hadwiger number at most two if and only if it is a forest

3

A graph has Hadwiger number at most three if and only if its treewidth is at most two, which is true if and only if each of its biconnected components is a series–parallel graph.

4

planar graphs have Hadwiger number at most four

5

The graphs with Hadwiger number at most five include the apex graphs and the linklessly embeddable graphs

Counts table

GraphDataCountTable["HadwigerNumber",Join[
(* 1s *)Thread[{"Empty"}->000012],
(* 2s *) Thread[{"Alkane","Centipede","LadderRung"}->007395],
(* 3s *)Thread[{"Cycle","Ladder","Pan","Sunlet"}->010701],
(* 4s *)Thread[{"Antiprism","Dipyramid","Gear","Helm","Prism","Web","Wheel","WheelComplement"}->010709],
(* 1,2,3,4,... *)Thread[{"Barbell","Complete","CompleteBipartite","Crown","Sun","TriangularHoneycombRook"}->000027],
(* 1,2,2,... *)Thread[{"Path","Star"}->040000],

{"CocktailParty"->032766,"PathComplement"->353212,"WheelComplement"->057353}
]]

Parametrized families

<<MathWorld`Graphs`

Alkane

seq=Table[GraphData[{"Alkane",n},"HadwigerNumber"],{n,10}]

FindSequenceFunction[seq,n]

AlternatingGroupGraph

seq=Table[GraphData[{"AlternatingGroupGraph",n},"HadwigerNumber"],{n,2,6}]

Andrasfai

seq=Table[GraphData[{"Andrasfai",n},"HadwigerNumber"],{n,10}]

Antelope n×n

seq=Table[GraphData[{"Antelope",{n,n}},"HadwigerNumber"],{n,15}]

Antiprism

Entity["Graph",{"Antiprism",n}]["HadwigerNumber"]

Inferred for n > 6:

seq=Table[GraphData[{"Antiprism",n},"HadwigerNumber"],{n,3,25}]

Do[Print[{GraphData[gn={"Antiprism",n},"#"],HadwigerNumber[GraphData[gn]]//Timing}],{n,3,10}]

Apollonian

seq=Table[GraphData[{"Apollonian",n},"HadwigerNumber"],{n,5}]

FindSequenceFunction[seq,n]

Barbell

seq=Table[GraphData[{"Barbell",n},"HadwigerNumber"],{n,3,20}]

FindSequenceFunction[seq,n]

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"HadwigerNumber"],{n,10}]

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"HadwigerNumber"],{n,10}]

Book

Inferred for n > 5:

seq=Table[GraphData[{"Book",n},"HadwigerNumber"],{n,20}]

Bruhat

seq=Table[GraphData[{"Bruhat",n},"HadwigerNumber"],{n,6}]

FindSequenceFunction[seq,n]

Camel n×n

seq=Table[GraphData[{"Camel",{n,n}},"HadwigerNumber"],{n,10}]

Centipede

seq=Table[GraphData[{"Centipede",n},"HadwigerNumber"],{n,10}]

FindSequenceFunction[seq,n]

CocktailParty

A032766

seq=Table[GraphData[{"CocktailParty",n},"HadwigerNumber"],{n,20}]

FullSimplify[FindSequenceFunction[seq,n],n∈Integers]

Complete

Entity["Graph",{"Complete",n}]["HadwigerNumber"]

seq=Table[GraphData[{"Complete",n},"HadwigerNumber"],{n,30}]

FindSequenceFunction[seq,n]

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["HadwigerNumber"]

CompleteBipartite n×n

Entity["Graph",{"CompleteBipartite",{n,n}}]["HadwigerNumber"]

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"HadwigerNumber"],{n,20}]

FindSequenceFunction[seq,n]//FullSimplify

CompleteTripartite k×m×n

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["HadwigerNumber"]

CompleteTripartite n×n×n

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["HadwigerNumber"]

seq=Table[GraphData[{"CompleteTripartite",{n,n,n}},"HadwigerNumber"],{n,10}]

FullSimplify[FindSequenceFunction[DeleteMissing@seq,n-1],n∈Integers]

Table[(1/4)  (6 n+5-(((-1))^n)),{n,10}]

CrossedPrism

seq=Table[GraphData[{"CrossedPrism",2n},"HadwigerNumber"],{n,2,10}]

FindSequenceFunction[seq,n-1]//Factor

Crown

Inferred for n > 5:

seq=Table[GraphData[{"Crown",n},"HadwigerNumber"],{n,20}]

Cycle

Entity["Graph",{"Cycle",n}]["HadwigerNumber"]

Inferred for n > 20:

seq=Table[GraphData[{"Cycle",n},"HadwigerNumber"],{n,3,30}]

Do[Print[{GraphData[gn={"Cycle",n},"#"],HadwigerNumber[GraphData[gn]]//Timing}],{n,3,25}]

CycleComplement

seq=Table[GraphData[{"CycleComplement",n},"HadwigerNumber"],{n,3,20}]

FullSimplify[FindSequenceFunction[seq,n-2],n∈Integers]

DiagonalIntersection

seq=Table[GraphData[{"DiagonalIntersection",n},"HadwigerNumber"],{n,3,14}]

Dipyramid

Inferred for n > 9:

seq=Table[GraphData[{"Dipyramid",n},"HadwigerNumber"],{n,3,20}]

Do[Print[{GraphData[gn={"Dipyramid",n},"#"],HadwigerNumber[GraphData[gn]]//Timing}],{n,3,10}]

Empty

Entity["Graph",{"Empty",n}]["HadwigerNumber"]

seq=Table[GraphData[{"Empty",n},"HadwigerNumber"],{n,30}]

FibonacciCube

seq=Table[GraphData[{"FibonacciCube",n},"HadwigerNumber"],{n,15}]

FindSequenceFunction[seq,n]//Head//Timing

Flower

seq=Table[GraphData[{"Flower",n},"HadwigerNumber"],{n,5,20}]

FoldedCube

seq=Table[GraphData[{"FoldedCube",n},"HadwigerNumber"],{n,2,10}]

FindSequenceFunction[seq,n]

Gear

Inferred for n > 7:

seq=Table[GraphData[{"Gear",n},"HadwigerNumber"],{n,3,20}]

Do[Print[{GraphData[gn={"Gear",n},"#"],HadwigerNumber[GraphData[gn]]//Timing}],{n,3,10}]

Giraffe n×n

seq=Table[GraphData[{"Giraffe",{n,n}},"HadwigerNumber"],{n,10}]

Goldberg

seq=Table[GraphData[{"FoldedCube",n},"HadwigerNumber"],{n,2,10}]

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["HadwigerNumber"]

Grid n×n

Entity["Graph",{"Grid",{n,n}}]["HadwigerNumber"]

seq=Table[GraphData[{"Grid",{n,n}},"HadwigerNumber"],{n,10}]

FindSequenceFunction[seq,n]

Grid k×m×n

Entity["Graph",{"Grid",{k,m,n}}]["HadwigerNumber"]

Sort@Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"HadwigerNumber"],
(((k+m+n) (k m n-1))/(3 k m n))
},{n,5},{m,n},{k,m}],2]

Tally[GraphData[{"Grid",{2,3,4}},"DistanceMatrix"]//Normal//Flatten]

Grid n×n×n

Entity["Graph",{"Grid",{n,n,n}}]["HadwigerNumber"]

seq=Table[GraphData[{"Grid",{n,n,n}},"HadwigerNumber"],{n,10}]

FindSequenceFunction[seq,n]//FullSimplify

HalvedCube

seq=Table[GraphData[{"HalvedCube",n},"HadwigerNumber"],{n,10}]

FindSequenceFunction[Rest@seq,n-1]

gf=x FindGeneratingFunction[seq,x]

SeriesCoefficient[gf,{x,0,n}]

Hanoi

seq=Table[GraphData[{"Hanoi",n},"HadwigerNumber"],{n,5}]

(seq=Table[HadwigerNumber[HanoiGraph[n]],{n,8}])//Timing

FindSequenceFunction[seq,n]//Head//Timing

FindSequenceFunction[Rest@seq,n-1]//Head//Timing

Helm

Inferred for n > 19:

seq=Table[GraphData[{"Helm",n},"HadwigerNumber"],{n,3,20}]

FindSequenceFunction[seq,n]

Hypercube

Entity["Graph",{"Hypercube",n}]["HadwigerNumber"]

seq=Table[GraphData[{"Hypercube",n},"HadwigerNumber"],{n,0,10}]

Do[Print[{GraphData[gn={"Hypercube",n},"#"],HadwigerNumber[GraphData[gn]]//Timing}],{n,10}]

Bound from

L. Sunil Chandrana, Naveen Sivadasan.  "On the Hadwiger’s conjecture for graph products."  Discrete Mathematics 307, 266–273, 2007.

TextGrid[Table[{d,ineq=Inactive[LessEqual][(2^(Floor[(d-1)/2])),GraphData[{"Hypercube",d},"HadwigerNumber"],Floor[(2^(d/2))(Sqrt[d])]+1],Activate@ineq},{d,7}],Dividers->All]

Keller

Entity["Graph",{"Keller",n}]["HadwigerNumber"]

seq=Table[GraphData[{"Keller",n},"HadwigerNumber"],{n,5}]

FindSequenceFunction[seq,n]

King n×n

seq=Table[GraphData[{"King",{n,n}},"HadwigerNumber"],{n,10}]

FindSequenceFunction[seq,n]//Factor

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["HadwigerNumber"]

Knight n×n

Entity["Graph",{"Knight",{n,n}}]["HadwigerNumber"]

seq=Table[GraphData[{"Knight",{n,n}},"HadwigerNumber"],{n,20}]

Ladder

Entity["Graph",{"Ladder",n}]["HadwigerNumber"]

Inferred for n > 7:

seq=Table[GraphData[{"Ladder",n},"HadwigerNumber"],{n,20}]

Do[Print[{GraphData[gn={"Ladder",n},"#"],HadwigerNumber[GraphData[gn]]//Timing}],{n,10}]

LadderRung

seq=Table[GraphData[{"LadderRung",n},"HadwigerNumber"],{n,20}]

MengerSponge

seq=Table[GraphData[{"MengerSponge",n},"HadwigerNumber"],{n,3}]

MoebiusLadder

Entity["Graph",{"MoebiusLadder",n}]["HadwigerNumber"]

Inferred for n > 8:

seq=Table[GraphData[{"MoebiusLadder",n},"HadwigerNumber"],{n,3,25}]

seq=Table[GraphData[{"MoebiusLadder",n},"MinorCount"],{n,3,25}]

{"MoebiusLadder", 9} needs 167+ GB

With[{debug=True},
Do[
gn=GraphData[{"MoebiusLadder",n},"#"];
If[debug,Print[gn]];
Print[{
gn,
HadwigerNumber[GraphData[gn],Debug->debug]//Timing
}],{n,3,10}]
]

Mycielski

Entity["Graph",{"Mycielski",n}]["HadwigerNumber"]

seq=Table[GraphData[{"Mycielski",n},"HadwigerNumber"],{n,11}]

Odd

Entity["Graph",{"Odd",n}]["HadwigerNumber"]

seq=Table[GraphData[{"Odd",n},"HadwigerNumber"],{n,7}]

FindSequenceFunction[Rest@seq,n-1]//Head//Timing

FindGeneratingFunction[seq,x]//Head//Timing

Pan

seq=Table[GraphData[{"Pan",n},"HadwigerNumber"],{n,3,20}]

Path

Entity["Graph",{"Path",n}]["HadwigerNumber"]

seq=Table[GraphData[{"Path",n},"HadwigerNumber"],{n,20}]

PathComplement

A353212

seq=Table[GraphData[{"PathComplement",n},"HadwigerNumber"],{n,20}]

seq=Table[GraphData[{"PathComplement",n},"MinorCount"],{n,20}]

FindSequenceFunction[DeleteMissing@seq,n]//Head//Timing

FindGeneratingFunction[DeleteMissing@seq,x]//Head//Timing

Do[Print[{GraphData[gn={"PathComplement",n},"#"],HadwigerNumber[GraphData[gn]]//Timing}],{n,20}]

Prism

Entity["Graph",{"Prism",n}]["HadwigerNumber"]

Inferred for n > 7:

seq=Table[GraphData[{"Prism",n},"HadwigerNumber"],{n,3,25}]

Do[Print[{GraphData[gn={"Prism",n},"#"],HadwigerNumber[GraphData[gn]]//Timing}],{n,3,10}]

Queen n×n

seq=Table[GraphData[{"Queen",{n,n}},"HadwigerNumber"],{n,10}]

FullSimplify[FindSequenceFunction[seq,n],n∈Integers]//Factor

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"HadwigerNumber"],{n,10}]

FullSimplify[FindSequenceFunction[seq,n],n∈Integers]//Factor

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"HadwigerNumber"],{n,10}]

FindSequenceFunction[Drop[seq,2],n-2]//Factor

SierpinskiCarpet

seq=Table[GraphData[{"SierpinskiCarpet",n},"HadwigerNumber"],{n,4}]

FindSequenceFunction[seq,n]

SierpinskiGasket

seq=Table[GraphData[{"SierpinskiGasket",n},"HadwigerNumber"],{n,5}]

SierpinskiTetrahedron

seq=Table[GraphData[{"SierpinskiTetrahedron",n},"HadwigerNumber"],{n,6}]

FindSequenceFunction[seq,n]

StackedBook

seq=Table[GraphData[{"StackedBook",{n,n}},"HadwigerNumber"],{n,10}]

StackedPrism

seq=Table[GraphData[{"StackedPrism",{n,n}},"HadwigerNumber"],{n,3,5}]

Star

Entity["Graph",{"Star",n}]["HadwigerNumber"]

seq=Table[GraphData[{"Star",n},"HadwigerNumber"],{n,25}]

Sun

Inferred for n > 6:

seq=Table[GraphData[{"Sun",n},"HadwigerNumber"],{n,3,20}]

FindSequenceFunction[seq,n-2]//Factor

Sunlet

seq=Table[GraphData[{"Sunlet",n},"HadwigerNumber"],{n,3,20}]

FullSimplify[FindSequenceFunction[seq,n-2],n∈Integers]

TorusGrid n×n

seq=Table[GraphData[{"TorusGrid",{n,n}},"HadwigerNumber"],{n,3,10}]

FullSimplify[FindSequenceFunction[seq,n-2],n∈Integers]

Transposition

Entity["Graph",{"Transposition",n}]["HadwigerNumber"]

seq=Table[GraphData[{"Transposition",n},"HadwigerNumber"],{n,6}]

Trapezohedron

Entity["Graph",{"Trapezohedron",n}]["HadwigerNumber"]

Inferred for n > 5:

seq=Table[GraphData[{"Trapezohedron",n},"HadwigerNumber"],{n,3,20}]

Triangular

seq=Table[GraphData[{"Triangular",n},"HadwigerNumber"],{n,2,10}]

TriangularGrid

seq=Table[GraphData[{"TriangularGrid",n},"HadwigerNumber"],{n,0,10}]

FindSequenceFunction[seq,n+1]//FullSimplify

TriangularHoneycombAcuteKnight

seq=Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"HadwigerNumber"],{n,20}]

TriangularHoneycombBishop

seq=Table[GraphData[{"TriangularHoneycombBishop",n},"HadwigerNumber"],{n,9}]

FindSequenceFunction[seq,n]//Factor

TriangularHoneycombObtuseKnight

seq=Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"HadwigerNumber"],{n,20}]

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"HadwigerNumber"],{n,10}]

FindSequenceFunction[seq,n]

TriangularHoneycombRook

seq=Table[GraphData[{"TriangularHoneycombRook",n},"HadwigerNumber"],{n,10}]

TriangularSnake

seq=Table[GraphData[{"TriangularSnake",n},"HadwigerNumber"],{n,1,20,2}]

Web

seq=Table[GraphData[{"Web",n},"HadwigerNumber"],{n,3,20}]

Wheel

Entity["Graph",{"Wheel",n}]["HadwigerNumber"]

Inferred for n > 14:

seq=Table[GraphData[{"Wheel",n},"HadwigerNumber"],{n,4,20}]

Do[Print[{GraphData[gn={"Wheel",n},"#"],HadwigerNumber[GraphData[gn]]//Timing}],{n,4,20}]

WheelComplement

A057353

https://arxiv.org/pdf/2204.10134v1.pdf

seq=Table[GraphData[{"WheelComplement",n},"HadwigerNumber"],{n,4,20}]

Table[Piecewise[{{1,n==4},{2,n==5}},Floor[((3(n-1))/4)]],{n,4,20}]==seq

Do[Print[{n,HadwigerNumber[GraphData[{"WheelComplement",n}]]//Timing}],{n,4,11}]

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"HadwigerNumber"],{n,2,10}]

Zebra n×n

seq=Table[GraphData[{"Zebra",{n,n}},"HadwigerNumber"],{n,10}]

Algorithms

<<MathWorld`Graphs`

DeleteCases[
Monitor[{
gn=#,
GraphData[#,"HadwigerNumber"],
HadwigerNumber[GraphData[#]]
}&/@GraphData[;;6],gn],
{_,x_,x_}]//Timing