Progress on Steinberg's Conjecture

This is a brief history of Steinberg's Conjecture, along with developments along the way, and links to recent papers.

Introduction

The Four Color Theorem implies that any planar graph can be colored with 4 colors without adjacent vertices receiving the same color. The number 4 is best possible, since K4 is planar and cannot be 3-colored. (This is also true for any wheel graph whose "hub" has odd degree.) Whether a graph requires 2 colors is easy to determine: If there are any cycles of odd length, the graph is not 2-colorable; otherwise it is. Thus the remaining problem for coloring planar graphs is determining which planar graphs can be 3-colored.

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 3-colored.

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.

[Not 3-colorable]

Progress Towards Steinberg's Conjecture

Paul Erdös suggested a way to make progress in 1991: To determine the smallest value of k, if it exists, such that a planar graph without any cycles of length 4, 5, ..., k can be 3-colored.

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:

3-Choosability

A graph G is 3-choosable if, for every assignment of sets with 3 elements to the vertices, there is a proper coloring where the vertex v is coloring using a color in its set. Hence 3-choosability implies 3-colorability; just let every set be {1,2,3}.

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:

Spiral Colorings

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.