Hadwiger conjecture (graph theory)
1657860
221053917
2008-06-22T21:19:38Z
David Eppstein
2051880
/* Generalizations */ snark theorem is for edge coloring
{{unsolved|mathematics|is every [[clique (graph theory)|''K<sub>k</sub>'']]-[[Minor (graph theory)|minor]]-free graph [[graph coloring|colorable]] with k − ''1'' colors?}}
[[Image:Hadwiger conjecture.svg|thumb|300px|A graph that requires four colors in any coloring, and four connected subgraphs that, when contracted, form a complete graph (each subgraph has an edge connecting it to each other subgraph), illustrating the case ''k'' = 4 of Hadwiger's conjecture]]
In [[graph theory]], the '''Hadwiger conjecture''' (or '''Hadwiger's conjecture''') states that, if an [[undirected graph]] ''G'' requires ''k'' or more colors in any [[graph coloring|vertex coloring]], then one can find ''k'' [[disjoint set|disjoint]] [[connected graph|connected]] [[subgraph]]s of ''G'' such that each subgraph is connected by an edge to each other subgraph. Contracting the edges within each of these subgraphs so that each subgraph collapses to a single supervertex produces a [[complete graph]] ''K<sub>k</sub>'' on ''k'' vertices as a [[minor (graph theory)|minor]] of ''G''.
This conjecture, a far-reaching generalization of the [[four-color problem]], was made by [[Hugo Hadwiger]] in [[1943]] and is still unsolved. {{harvtxt|Bollobás|Catlin|Erdős|1980}} call it “one of the deepest unsolved problems in graph theory.”<ref name="BolCatErd1980" />
==Equivalent forms==
An equivalent form of the Hadwiger conjecture (the [[contrapositive]] of the form stated above) is that, if there is no sequence of [[edge contraction]]s (each merging the two endpoints of some edge into a single supervertex) that brings graph ''G'' to the complete graph ''K<sub>k</sub>'', then ''G'' must have a vertex coloring with ''k'' − 1 colors.
Note that, in a [[complete coloring|minimal]] ''k''-coloring of any graph ''G'', contracting each color class of the coloring to a single vertex will produce a complete graph ''K<sub>k</sub>''. However, this contraction process does not produce a minor of ''G'' because the contracted sets of vertices are not in general connected. Hadwiger's conjecture states that there exists a different way of contracting sets of vertices to single vertices, producing a complete graph ''K<sub>k</sub>'', in such a way that all the contracted sets are connected.
If ''F<sub>k</sub>'' denotes the family of graphs having the property that all minors of graphs in ''F<sub>k</sub>'' can be (''k'' − 1)-colored, then it follows from the [[Robertson–Seymour theorem]] that ''F<sub>k</sub>'' can be characterized by a finite set of [[Forbidden graph characterization|forbidden minors]]. Hadwiger's conjecture is that this set consists of a single forbidden minor, ''K<sub>k</sub>''.
==Special cases==
The case where ''k'' = 2 is trivial: a graph requires more than one color if and only if it has an edge, and that edge is itself a ''K''<sub>2</sub> minor. The case ''k'' = 3 is also easy: the graphs requiring three colors are the non-[[bipartite graph]]s, and every non-bipartite graph has an odd [[cycle (graph theory)|cycle]], which can be contracted to a 3-cycle, that is, a ''K''<sub>3</sub> minor.
In the same paper in which he introduced the conjecture, Hadwiger proved its truth for ''k'' ≤ 4. The graphs with no ''K''<sub>4</sub> minor are the [[series-parallel graph]]s and their subgraphs. Each graph of this type has a vertex with at most two incident edges; one can 3-color any such graph by removing one such vertex, coloring the remaining graph recursively, and then adding back and coloring the removed vertex. Because the vertex has at most two edges, one of the three colors will always be available to color it.
The truth of the conjecture for ''k'' = 5 implies the [[four color theorem]]: for, if the conjecture is true, every graph requiring five or more colors would have a ''K''<sub>5</sub> minor and would (by [[Wagner's theorem]]) be nonplanar.
[[Klaus Wagner (mathematician)|Klaus Wagner]] proved in [[1937]] that the case ''k'' = 5 is actually equivalent to the four color theorem and therefore we now know it to be true. As Wagner showed, every graph that has no ''K''<sub>5</sub> minor can be decomposed via [[clique-sum]]s into pieces that are either planar or an 8-vertex [[Möbius ladder]], and each of these pieces can be 4-colored independently of each other, so the 4-colorability of a ''K''<sub>5</sub>-free graph follows from the 4-colorability of each of the planar pieces.
{{harvtxt|Robertson|Seymour|Thomas|1993}} proved the conjecture for ''k'' = 6, also using the four color theorem. Thus the conjecture is true for ''k'' ≤ 6 but it remains unsolved for all ''k'' > 6.
For ''k'' = 7, some partial results are known: every 7-chromatic graph must contain either a ''K''<sub>7</sub> minor or both a ''K''<sub>4,4</sub> minor and a ''K''<sub>3,5</sub> minor.<ref>The existence of either a ''K''<sub>7</sub> or ''K''<sub>3,5</sub> minor was shown by Kawarabayashi, and {{harvtxt|Kawarabayashi|Toft|2005}} proved the existence of either a ''K''<sub>7</sub> or ''K''<sub>4,4</sub> minor.</ref>
==Hadwiger number==
The '''Hadwiger number''' ''h''(''G'') of a graph ''G'' is the size ''k'' of the largest complete graph ''K<sub>k</sub>'' that is a minor of ''G'' (or equivalently can be obtained by contracting edges of ''G''). It is also known as the '''contraction clique number''' of ''G''.<ref name="BolCatErd1980">{{harvtxt|Bollobás|Catlin|Erdős|1980}}.</ref> The Hadwiger conjecture can be stated in the simple algebraic form ''χ''(''G'') ≤ ''h''(''G'') where ''χ''(''G'') denotes the [[chromatic number]] of ''G''. A related concept, the [[Complete coloring|achromatic number]] of ''G'', is the size of the largest clique that can be formed by contracting a family of [[independent set]]s in ''G'').
Determining the Hadwiger number of a given graph is [[Parameterized complexity|fixed-parameter tractible]]: there is an algorithm for finding the largest clique minor in an amount of time that depends only polynomially on the size of the graph, but exponentially in ''h''(''G'').<ref>{{harvtxt|Alon|Lingas|Wahlen|2006}}.</ref> {{harvtxt|Alon|Lingas|Wahlen|2006}} consider approximation algorithms for finding large clique minors in graphs, and observe that (unless [[P=NP]]) polynomial time algorithms can approximate the Hadwiger number significantly more accurately than the best possible approximation to the size of the largest clique in a graph.
It is known that every graph ''G'' with ''h''(''G'') = ''k'' has a vertex with at most O(k √log ''k'') incident edges.<ref>{{harvtxt|Kostochka|1984}}. The letter O in this expression invokes [[big O notation]].</ref> By removing this low-degree vertex, coloring the remaining graph, and then adding back the removed vertex and coloring it, one can show that ''χ''(''G'') = O(k √log ''k'').
==Generalizations==
György Hajós conjectured that Hadwiger's conjecture could be strengthened to [[Homeomorphism (graph theory)|subdivisions]] rather than minors: that is, that every graph with chromatic number ''k'' contains a subdivision of a complete graph ''K<sub>k</sub>''. Hajós' conjecture is true for ''k'' ≤ 4, but {{harvtxt|Catlin|1979}} found counterexamples to this strengthened conjecture for ''k'' ≥ 7; the cases ''k'' = 5 and ''k'' = 6 remain open.<ref>{{harvtxt|Yu|Zickfeld|2006}}.</ref> {{harvtxt|Erdős|Fajtlowicz|1981}} observed that Hajós' conjecture fails badly for [[random graph]]s: for any ε > 0, in the limit as the number of vertices, ''n'', goes to infinity, the probability approaches one that a random ''n''-vertex graph has chromatic number ≥ (1/2 − ε)''n'' / log<sub>2</sub> ''n'', and that its largest clique subdivision has at most ''cn''<sup>1/2</sup> vertices for some constant ''c''. In this context it is worth noting that the probability also approaches one that a random ''n''-vertex graph has Hadwiger number greater than or equal to its chromatic number, so the Hadwiger conjecture holds for random graphs with high probability; more precisely, the Hadwiger number is with high probability a constant times ''n''/√log ''n''.<ref>{{harvtxt|Bollobás|Catlin|Erdős|1980}}.</ref>
Gerards and Seymour conjectured that every graph ''G'' with chromatic number ''k'' has a complete graph ''K<sub>k</sub>'' as an ''odd minor''. Such a structure can be represented as a family of ''k'' vertex-disjoint subtrees of ''G'', each of which is two-colored, such that each pair of subtrees is connected by a monochromatic edge. Although graphs with no odd ''K<sub>k</sub>'' minor are not necessarily [[sparse graph|sparse]], a similar upper bound holds for them as it does for the standard Hadwiger conjecture: a graph with no odd ''K<sub>k</sub>'' minor has chromatic number ''χ''(''G'') = O(k √log ''k'').<ref>{{harvtxt|Geelen|Gerards|Reed|Seymour|2006}}; Kawarabayashi (to appear in ''JCTB'').</ref>
By imposing more conditions on ''G'' than the number of colors it needs, it may be possible to prove the existence of larger minors than ''K<sub>k</sub>''. One example of this is the [[Snark (graph theory)|snark theorem]], that every [[cubic graph]] requiring four colors in any [[edge coloring]] has the [[Petersen graph]] as a minor, conjectured by [[W. T. Tutte]] and announced to be proved in 2001 by Robertson, Sanders, Seymour, and Thomas.<ref>{{citation|last=Pegg|first=Ed, Jr.|authorlink=Ed Pegg, Jr.|title=Book Review: The Colossal Book of Mathematics|journal=Notices of the American Mathematical Society|volume=49|issue=9|year=2002|pages=1084–1086|url=http://www.ams.org/notices/200209/rev-pegg.pdf}}.</ref>
==Notes==
{{reflist|2}}
==References==
*{{citation | last1 = Alon | first1 = Noga | authorlink1 = Noga Alon | last2 = Lingas | first2 = Andrzej | last3 = Wahlen | first3 = Martin | title = Approximating the maximum clique minor and some subgraph homeomorphism problems | journal = Theoretical Computer Science | volume = 374 | issue = 1–3 | year = 2007 | pages = 149–158 | doi = 10.1016/j.tcs.2006.12.021 | url = http://www.math.tau.ac.il/~nogaa/PDFS/lingas7.pdf}}.
*{{citation | last1 = Bollobás | first1 = B. | authorlink1 = Bela Bollobás | last2 = Catlin | first2 = P. A. | last3 = Erdős | first3 = Paul | authorlink3 = Paul Erdős | title = Hadwiger's conjecture is true for almost every graph | journal = European Journal on Combinatorics | volume = 1 | year = 1980 | pages = 195–199 | url = http://www2.renyi.hu/~p_erdos/1980-10.pdf}}.
*{{citation | last = Catlin | first = P. A. | title = Hajós's graph-colouring conjecture: variations and counterexamples | journal = Journal of Combinatorial Theory, Series B | volume = 26 | year = 1979 | pages = 268–274}}.
*{{citation | last1 = Erdős | first1 = Paul | authorlink1 = Paul Erdős | last2 = Fajtlowicz | first2 = Siemion | title = On the conjecture of Hajós | journal = Combinatorica | volume = 1 | issue = 2 | year = 1981 | pages = 141–143 | doi = 10.1007/BF02579269}}.
*{{citation | last1 = Geelen | first1 = Jim | last2 = Gerards | first2 = Bert | last3 = Reed | first3 = Bruce | last4 = Seymour | first4 = Paul | author4-link = Paul Seymour (mathematician) | last5 = Vetta | first5 = Adrian | year = 2006 | title = On the odd-minor variant of Hadwiger's conjecture | url = http://homepages.cwi.nl/~bgerards/personal/papers/geelen_gerards_goddyn_reed_seymour_vetta:odd_hadwicher%5B2006%5Dpre.ps}}. ''Journal of Combinatorial Theory, Series B'', in press.
*{{citation | last1=Hadwiger | first1=Hugo | author1-link=Hugo Hadwiger | title=Über eine Klassifikation der Streckenkomplexe | year=1943 | journal=Vierteljschr. Naturforsch. ges. Zürich | volume=88 | pages=133–143}}.
*{{citation | last=Kawarabayashi | first=Ken-ichi | title = Minors in 7-chromatic graphs | publisher = Preprint}}.
*{{citation | last=Kawarabayashi | first=Ken-ichi | title = Note on coloring graphs without odd ''K<sub>k</sub>''-minors | publisher = Preprint}}. To appear in ''Journal of Combinatorial Theory, Series B''.
*{{citation | last1=Kawarabayashi | first1 = Ken-ichi | last2 = Toft | first2 = Bjarne | title = Any 7-chromatic graph has ''K''<sub>7</sub> or ''K''<sub>4,4</sub> as a minor | journal = Combinatorica | volume = 25 | issue = 3 | pages = 327–353 | year = 2005 | doi = 10.1007/s00493-005-0019-1}}.
*{{citation | last = Kostochka | first = A. V. | title = Lower bound of the Hadwiger number of graphs by their average degree | journal = Combinatorica | volume = 4 | issue = 4 | pages = 307–316 | year = 1984 | doi = 10.1007/BF02579141}}.
*{{citation | last1=Robertson | first1=Neil | author1-link=Neil Robertson (mathematician) | last2=Seymour | first2=Paul | author2-link=Paul Seymour (mathematician) | last3=Thomas | first3=Robin | title=Hadwiger's conjecture for K<sub>6</sub>-free graphs | url=http://www.math.gatech.edu/~thomas/PAP/hadwiger.pdf | year=1993 | journal=Combinatorica | volume=14 | pages=279–361}}.
*{{citation | last=Wagner | first=Klaus | authorlink=Klaus Wagner (mathematician) | title=Über eine Eigenschaft der ebenen Komplexe | journal = Mathematische Annalen | volume = 114 | pages = 570–590 | year = 1937}}.
*{{citation | last1 = Yu | first1 = Xingxing | last2 = Zickfeld | first2 = Florian | title = Reducing Hajós' 4-coloring conjecture to 4-connected graphs | journal = Journal of Combinatorial Theory, Series B | volume = 96 | issue = 4 | year = 2006 | doi = 10.1016/j.jctb.2005.10.001 | pages = 482–492}}.
[[Category:Graph coloring]]
[[Category:Conjectures]]
[[fr:Conjecture d'Hadwiger]]