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 K2 minor. The case k = 3 is also easy: the graphs requiring three colors are the non-bipartite graphs, and every non-bipartite graph has an odd cycle, which can be contracted to a 3-cycle, that is, a K3 minor.
In the same paper in which he introduced the conjecture, Hadwiger proved its truth for k ≤ 4. The graphs with no K4 minor are the series-parallel graphs 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 removed vertex has at most two edges, one of the three colors will always be available to color it when the vertex is added back.
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 K5 minor and would (by Wagner's theorem) be nonplanar. 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 K5 minor can be decomposed via clique-sums 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 K5-minor-free graph follows from the 4-colorability of each of the planar pieces.
Robertson, Seymour & Thomas (1993) proved the conjecture for k = 6, also using the four color theorem; their paper with this proof won the 1994 Fulkerson Prize. It follows from their proof that linklessly embeddable graphs, a three-dimensional analogue of planar graphs, have chromatic number at most five. Due to this result, the conjecture is known to be 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 K7 minor or both a K4,4 minor and a K3,5 minor.
Read more about this topic: Hadwiger Conjecture (graph Theory)
Famous quotes containing the words special and/or cases:
“When a mother quarrels with a daughter, she has a double dose of unhappiness—hers from the conflict, and empathy with her daughter’s from the conflict with her. Throughout her life a mother retains this special need to maintain a good relationship with her daughter.”
—Terri Apter (20th century)
“We noticed several other sandy tracts in our voyage; and the course of the Merrimack can be traced from the nearest mountain by its yellow sand-banks, though the river itself is for the most part invisible. Lawsuits, as we hear, have in some cases grown out of these causes. Railroads have been made through certain irritable districts, breaking their sod, and so have set the sand to blowing, till it has converted fertile farms into deserts, and the company has had to pay the damages.”
—Henry David Thoreau (1817–1862)