The graph K4 has served as the prototype for a planar graph requiring 4 colors. The search for which properties it has has led to results stating when a planar graph is 3-colorable.
A result by Brooks implies that every connected graph G where every vertex is adjacent to at most 3 vertices is 3-colorable, unless G is K4.
Grötzsch proved that if G is a triangle-free planar graph, then G is 3-colorable. In fact, any planar graph with fewer than 4 triangles is 3-colorable, as was proven by Grünbaum in 1963. ("Grötzsch's theorem on 3-colorings", Michigan Math. J. 10, 303-310.) Note that there is a graph similar to the figure below which has four triangles but is not 3-colorable. (V. A. Aksionov, L. S. Melnikov, "Some Counterexamples Associated with the Three-Color Problem", JCT-B 28, 1-9 (1980).)
Another property that K4 has is that it contains a cycle of length 4, so a natural question is whether planar graphs without 4-cycles can be 3-colored. Unfortunately, the answer is no, due to the graph below, so the next natural question is whether a graph without 4-cycles and 5-cycles is 3-colorable. This is Steinberg's Conjecture, proposed by Richard Steinberg in 1976 and listed as an unsolved problem in T. R. Jensen and B. Toft's Graph Coloring Problems (1995).
|Figure (right): A planar graph without 4-cycles that cannot be
The graphs which have been inserted between the verices u and v and between the vertices v and w simulate the edges uv and vw. That is, if you 3-color this subgraph, the vertices marked u and v will receive the same color.
This subgraph shows why Steinberg's Conjecture assumes that there are no 4- or 5-cycles.
Paul Erdös's question can be asked about other surfaces. Surprisingly, for any surface Σ, there exists a k such that if G is a graph embedding on Σ and G has no cycles of length 4 through k, then G is 3-colorable. This was proven by Yue Zhao in 2000. (Y. Zhao, "3-coloring graphs embedded in surfaces." J. Graph Theory 33, no. 3, 140-143.)
Several papers which study the structure of Steinberg-type graphs are:
In this paper, he shows: If in a plane graph with minimum degree 3 no two triangles have an edge in common, then: (1) there are two adjacent vertices with degree sum at most 9, and (2) there is a face of size between 4 and 9 or a 10-face incident with ten 3-vertices. It follows that every planar graph without cycles between 4 and 9 is 3-colorable.
In this paper, they show: Planar graphs without 3-cycles at distance less than 4 and without 5-cycles are proved to be 3-colorable. They conjecture that, moreover, each plane graph with neither 5-cycles nor intersecting 3-cycles is 3-colorable. In this conjecture, none of the two assumptions can be dropped because there exist planar 4-chromatic graphs without 5-cycles, as well as planar 4- chromatic graphs without intersecting triangles. (Also, when "3-colorable" is replaced with "3-choosable", the conjecture is false; see the Montassier/Raspaud/Wang paper in the "3-choosability" section below.)
This result was strengthened by Baogang Xu from "distance less than 4" to "distance less than 3". (This paper appeared in Acta Math. Sinica.)
Xu shows that every plane graph without 5- and 7-cycles and without adjacent triangles (two triangles which have at least one vertex in common) is 3-colorable.
Their paper has two useful lemmas about the number of edges in a Steinberg-type graph:
The bad news is that not every graph without 4- and 5-cycles is 3-choosable, so there is no direct route from 3-choosability to 3-colorability. (One such graph is given by Margit Voigt in "A non-3-choosable planar graph without cycles of length 4 and 5", Discrete Mathematics 307 No. 7 & 8 (2007) 1013-1015.) However, there are some results which prove 3-choosability of a class of graphs:
Any planar graph without 3-, 5- and 6-cycles is 3-choosable.
Any planar graph without 4-, 5-, 6-, and 9-cycles is 3-choosable.
Any graph without 4-, 5-, 7-, and 9-cycles is 3-choosable.
A graph with no 4-, or 5-cycles, and no triangles at a distance of less than 4, is 3-choosable. A graph with no 4-, 5-, or 6-cycles, and no triangles at a distance of less than 3, is 3-choosable. There is a graph without 4- or 5-cycles, no intersection triangles, which is not 3-choosable.
Ibrahim Cahit claims to have a proof of Steinberg's Conjecture, where he uses Spiral Colorings. I have two reasons to doubt the validity of this proof: (1) In the version of the paper I read, everything was "window dressing" except the single sentence: Suppose there is a counterexample G; then G must be [one particular graph]. This is stated without proof. (2) He claims to have proofs of results about 3-colorability for which counterexamples are known, several being from the paper by Aksionov and Melnikov above.
Spiral colorings might be a good heuristic for coloring planar graphs, but his proofs (of the Four Color Theorem, Steinberg's Conjecture, etc) do not have enough detail to convince me that the proofs are complete.
This page is updated by Christopher Carl Heckman. Last updated April 2007.