# 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.

## 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.

• H. L. Abbott and Bing Zhou showed, in "On small faces in 4-critical graphs", Ars Combin. 32 (1991), that k ≤ 11.

• Daniel P. Sanders and Yue Zhao showed, in "A note on the three color problem", Graphs and Combinatorics 11 (1995), 91-94, that k ≤ 9.

• Mohammad Salavatipour showed, in "The Three Color Problem for Planar Graphs", Technical Report CSRG-458, Department of Computer Science, University of Toronto, July 2002, that k ≤ 8. [available here]

• O. V. Borodin, A. N. Glebov, A. Raspaud, and M. R. Salavatipour showed, in "Planar Graphs without Cycles of Length from 4 to 7 are 3-colorable", J. of Combinatorial Theory (Series B), 93:303-311, 2005, that k ≤ 7. [available here]

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:

• O. V. Borodin, "Structural properties of plane graphs without adjacent triangles and an application to 3-colorings", J. of Graph theory 21 (1996), 183-186.

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.

• O. V. Borodin, A. Raspaud, "A sufficient condition for planar graphs to be 3-colorable", Journal of Combinatorial Theory Series B Volume 88 , Issue 1 (May 2003), pp. 17-27.

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.)

• Baogang Xu, "On 3-colorable plane graphs without 5- and 7-cycles", Journal of Combinatorial Theory, Series B 96 (2006) 958-963.

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.

• Peter Che Bor Lam, Jiazhuang Liu, Wai Chee Shiu, Jianliang Wu, "Some sufficient conditions for a planar graph to be of Class 1", Congress. Numer. 136, 201-205 (1999). [available here]

Their paper has two useful lemmas about the number of edges in a Steinberg-type graph:

• Lemma 2. If k ≥ 4, and G is a connected planar graph without 2 triangles sharing a common edge, and without i-cycles for all i: 3 < i < k, then
[NOTE: This bound might not be sharp.]

• Lemma 3. Same conditions above, if no two 3-cycles share a common vertex,
[NOTE: In the statement of Lemma 3 in this paper, "v" is omitted.]

## 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:

• P. Lam, Wai Chee Shiu, Zeng Min Song, B. Xu, "The 3-choosability of plane graphs of girth 4", Discrete Mathematics 294 (2005) 297-301.

Any planar graph without 3-, 5- and 6-cycles is 3-choosable.

• L. Zhang, B. Wu, "A note on 3-choosability of planar graphs without certain cycles", Discrete Mathematics 297 (2005) 206-209. [available here]

Any planar graph without 4-, 5-, 6-, and 9-cycles is 3-choosable.

• L. Zhang, B. Wu, "Three-choosable planar graphs without certain small cycles", Graph Theory Notes New York 46 (2004) 27-30.

Any graph without 4-, 5-, 7-, and 9-cycles is 3-choosable.

• Mickaël Montassier, André Raspaud, Weifan Wang, "Bordeaux 3-color conjecture and 3-choosability", Discrete Mathematics 306 (2006) 573-579. [available here]

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.

## 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.