The 3-Color Problem (last modification: 25-01-2011)

Once upon a time The 3-Color Problem

In 1976, Appel and Haken proved that every planar graph is 4-colorable ; this problem was posed by Francis Guthrie in 1852. The characterization of 2-colorable graphs is easy to determine: it corresponds exactly to graphs without odd cycles. The remaining problem is to determine which planar graphs are 3-colorable. As proved by Garey et al., the problem of deciding whether a planar graph is 3-colorable is NP-complete. Therefore, some sufficient conditions for planar graphs to be 3-colorable were stated. As early as 1959, Grötzsch proved that every planar graph without 3-cycles is 3-colorable. This result was later improved by Aksionov in 1974. He proved that every planar graph with at most three 3-cycles is 3-colorable. In 1976, Steinberg conjectured the following :

Steinberg's Conjecture '76: Every planar graph without 4- and 5-cycles is 3-colorable.

In 1969, Havel posed the following problem:

Havel's Problem '69: Does there exist a constant C such that every planar graph with the minimal distance between triangles at least C is 3-colorable?

Aksionov and Mel'nikov proved that if C exists, then C >= 4, and conjectured that C=5. Recently [2009], Dvorak, Kral, and Thomas proved the existence of C.

Erdös suggested the following relaxation of Steinberg's Conjecture: Determine the smallest value of k, if it exists, such that every planar graph without any cycles of length 4 to k is 3-colorable. The best known bound for such a k is 7. Many other sufficient conditions of 3-colorability considering planar graphs without cycles of specific lengths were proposed.

At the crossroad of Havel's and Steinberg's problems (since the authors consider planar graphs without cycles of specific length and without close triangles), Borodin and Raspaud proved that every planar graph without 3-cycles at distance less than four and without 5-cycles is 3-colorable (the distance was later decreased to three by Xu, and to two by Borodin and Glebov). As well, they proposed the following conjecture:

Strong Bordeaux Conjecture '03: Every planar graph without 5-cycles and without adjacent triangles is 3 colorable.

By adjacent cycles, we mean those with an edge in common. This conjecture implies Steinberg's Conjecture. Finally, Borodin et al. considered the adjacency between cycles in planar graphs where all lengths of cycles are authorized, which seems to be the closest from Havel's problem ; they proved that every planar graphs without triangles adjacent to cycles of length from 3 to 9 is 3-colorable. Moreover they proposed the following conjecture:

Novosibirsk 3-Color Conjecture '06: Every planar graph without 3-cycles adjacent to cycles of length 3 or 5 is 3-colorable.

This implies Strong Bordeaux Conjecture and Steinberg's Conjecture.

In the following, we give references for results and problems on The 3-Color Problem.

The state of the three color problem.
R. Steinberg. Quo Vadis, Graph Theory? Annals of Discrete Mathematics, 55:211-248, 1993.

Planar graphs without prescribed cycles

Every planar graph without 3-cycles is 3 colorable.
H. Grötzsch. Ein Dreifarbenzatz für dreikreisfreie netze auf der kugel. Math.-Natur. Reihe, 8:109--120, 1959.
V.A. Aksionov. Chromatic connected vertices in planar graphs. Diskret. Analiz 31:5--16, 1977 (in Russian).
C. Thomassen. Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane. J. Combin. Theory Ser. B 62:268--279, 1994.
C. Thomassen. 3-list-coloring planar graphs of girth 5. J. Combin. Theory Ser. B 64(1):101--107, 1995.
T.R. Jensen and C. Thomassen. The color space of a graph. Journal of Graph Theory, 34(3):234--245, 2000.
V.A. Aksenov, O.V. Borodin, A.N. Glebov. On extending 3-colorability from two vertices in a planar triangle-free graph. Diskretn. Anal. Issled. Oper 9(1):3--26, 2002. (in russian.)
C. Thomassen. The chromatic number of a graph of girth 5 on a fixed surface. J. Combin. Theory Ser. B 87:38--71, 2003.
C. Thomassen. A short list color proof of Grötzsch's theorem. J. Combin. Theory Ser. B 88:189--192, 2003.
V.A. Aksenov, O.V. Borodin, A.N. Glebov. On extending 3-colorability from a 6-face to a planar triangle-free graph. Diskretn. Anal. Issled. Oper. 10(3):3--11, 2003. (in russian.)
V.A. Aksenov, O.V. Borodin, A.N. Glebov. On extending 3-colorability from a 7-face to a planar triangle-free graph. Sib. Elektron. Mat. Izv. 1:117--128, 2004. (in russian.)
Z. Dvorak, K-I. Kawarabayashi, R. Thomas. Three-coloring triangle-free planar graphs in linear time. Manuscript 2008.

Every planar graph with girth at least 5 is 3-choosable.
C. Thomassen. 3-list-coloring planar graphs of girth 5. J. Combin. Theory Ser. B 64(1):101--107, 1995.
C. Thomassen. A short list color proof of Grötzsch's theorem. J. Combin. Theory Ser. B 88:189--192, 2003.
Z. Dvorak, K.I. Kawarabayashi. Choosability of planar graphs with girth 5. Manuscript, 2010. (here)

Every planar graph with at most three 3-cycles is 3-colorable.
B. Grünbaum. Grötzsch's theorem on 3-colorings. Michigan Math. J., 10(3):303--310, 1963.
V.A. Aksionov. On continuation of 3-coloring of planar graph. Diskret. Analiz. 26:3--19, 1974 (in Russian).
O.V. Borodin. New proof of Grunbaum's 3-colour Theorem. Discrete Mathematics, 169:177--183, 1997.

Every planar graph without cycles of lengths 4 to 11 is 3-colorable.
H.L. Abbott, B. Zhou. On small faces in 4-critical graphs. Ars Combin. 32:203--207, 1991.

Every planar graph without cycles of lengths 4 to 10 is 3-colorable.
O.V. Borodin. To the paper of H.L. Abbott and B. Zhou on 4-critical planar graphs.Ars Combin. 43:191-192, 1996.

Every planar graph without cycles of lengths 4 to 9 is 3-colorable.
D.P. Sanders and Y. Zhao. A note on the three color problem. Graphs and Combinatorics, 11:91--94, 1995.
O.V. Borodin. Structural properties of plane graphs without adjacent triangles and an application to 3-colorings. Journal of Graph Theory, 21(2):183--186, 1996.

Every planar graph without cycles of lengths 4 to 8 is 3-colorable.
M.R. Salavatipour. The Three Color Problem For Planar Graphs. Technical Report CSRG-458, Department of Computer Science, University of Toronto, 2002.

Every planar graph without cycles of lengths 4 to 7 is 3-colorable.
O.V. Borodin, A.N. Glebov, A. Raspaud, and M.R. Salavatipour. Planar graphs without cycles of length from 4 to 7 are 3-colorable. Journal of Combinatorial Theory, Series B, 93:303--311, 2005.

Every planar graph without cycles of lengths 4,5,7 is 3-colorable.
B. Xu. On 3-colorable plane graphs without 5- and 7-cycles. Journal of Combinatorial Theory, Series B, 96:958--963, 2006.
See: http://arxiv.org/abs/0810.1437
O.V. Borodin, A.N. Glebov, M. Montassier, and A. Raspaud. Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable.In Journal of Combinatorial Theory, Series B, 99:668--673, 2009.

Let G be a planar graph without 4-,6-,7-cycles and without two 5-cycles sharing exactly one edge, then G 3-colorable.
M. Chen and W. Wang.On 3-colorable planar graphs without short cycles. Appl. Math. Letter 21(9):961-965, 2008.

Every planar graph without cycles of lengths 4,5,6,8 is 3-colorable.
M. Chen and W. Wang. On 3-colorable planar graphs without prescribed cycles. Discrete Mathematics, 307:2820--2825, 2007.

Every planar graph without cycles of lengths 4,6,7,8 is 3-colorable.
L. Xiaofang, M. Chen and W. Wang. On 3-colorable planar graphs without cycles of four lengths. Information Processing Letters, 103:150-156, 2007.

Every planar graph without cycles of lengths 4,6,8 is 3-colorable.
M. Chen and W. Wang. Planar graphs without 4,6,8-cycles are 3-colorable. Science in China Series A: Mathematics, 50(11):1552-1562, 2007.

Every planar graph without cycles of lengths 4,6,7,9 is 3-colorable.
M. Chen, A. Raspaud, and W. Wang. Three-coloring planar graphs without short cycles. Information Processing Letters, 101:134--138, 2007.

There exist non 3-choosable planar graphs without cycles of length 3.
M. Voigt. A not 3-choosable planar graph without 3-cycles. Discrete Mathematics, 146(1-3):325-328, 1995.

There exist non 3-choosable planar graphs without cycles of length 4 and 5.
M. Voigt. A non-3-choosable planar graph without cycles of length 4 and 5.Discrete Mathematics, 307(7-8):1013-1015, 2007.

Every planar graph without cycles of lengths 4,5,6,9 is 3-choosable.
L. Zhang, B. Wu. A note on 3-choosability of planar graphs without certain cycles. Discrete Mathematics, 297:206--209, 2005.

Every planar graph without cycles of lengths 4,6,8,9 is 3-choosable.
L. Shen and Y. Wang. A sufficient condition for a planar graph to be 3-choosable. Information Processing Letters, 104:146--151, 2007.

Every planar graph without cycles of lengths 4,5,7,9 is 3-choosable.
L. Zhang and B. Wu. Three-coloring planar graphs without certain small cycles. Graph Theory Notes of New York, 46:27--30, 2004.

Every planar graph without cycles of lengths 4,6,7,9 is 3-choosable.
M. Chen, H. Lu, and Y. Wang. A note on 3-choosability of planar graphs. Information Processing Letters, 105(5):206--211, 2008.

Every planar graph without cycles of lengths 4,5,8,9 is 3-choosable.
Y. Wang et al. Planar graphs without cycles of length 4,5,8 or 9 are 3-choosable. Submitted, 2007.

Every planar graph without cycles of lengths 4,7,8,9 is 3-choosable.
M. Chen, L. Shen, and Y. Wang. Planar graphs without cycles of length 4,7,8 or 9 are 3-choosable. Submitted, 2007.

Every planar graph without cycles of lengths 3,5,6 is 3-choosable.
P.C.B. Lam, W.C. Shiu, Z.M. Song, and B. Xu. The 3-choosability of plane graphs of girth 4. Discrete Mathematics 294(3):297--301, 2005.

Every planar graph without cycles of lengths 3,6,7,9 is 3-choosable.
H. Zhang, and B. Xu. On the 3-choosability of plane graphs without 6-,7- and 9-cycles. Appl. Math. J. Chinese Univ. Ser. B 19(1):109--115, 2004.

Every planar graph without cycles of lengths 3,5,8,9 is 3-choosable.
H. Zhang. On the 3-choosability of plane graphs without 5-,8- and 9-cycles. J. Lanzhou Univ. Nat. Sci. 41(3):93--97,2005

Every planar graph without cycles of lengths 3,6,7,8 is 3-choosable.
B. Lidicky. On the 3-choosability of plane graphs without 6-,7- and 8-cycles. Manuscript, 2008.

Every planar graph without cycles of lengths 3,7,8 is 3-choosable.
Z. Dvorak, B. Lidicky, and R. Skrekovski. Plane graphs without 3-,7-, and 8-cycles are 3-choosable. Manuscript, 2008.

Every planar graph without cycles of lengths 3,6,7 is 3-choosable.
Z. Dvorak, B. Lidicky, and R. Skrekovski. On 3-choosability of plane graphs without 3-, 6- and 7-cycles. Manuscript, 2008.

Every planar graph without cycles of lengths 3,8,9 is 3-choosable.
H. Zhang, B. Xu, and Z. Sun. Every plane graph with girth at least 4 without 8- and 9-circuits is 3-choosable. Ars Combin. 80:247--257, 2006.
X. Zhu, M. Lianying, and C. Wang. On 3-choosability of plane graphs without 3-,8-, and 9-cycles. Australas. J. Comb. 38:249--254, 2007.

Planar graphs without close cycles

If C exists, then C>3.
V.A. Aksionov and L.S. Mel'nikov. Some counterexamples associated with the Three Color Problem. Journal of Combinatorial Theory, Serie B, 28(1):1--9, 1980.

Every planar graph without cycles of length 5 and without triangles at distance less than 4 is 3-colorable.
O.V. Borodin and A. Raspaud. A sufficient condition for a planar graph to be 3-colorable. Journal of Combinatorial Theory, Serie B, 88:17--27, 2003.

Every planar graph without cycles of length 5 and without triangles at distance less than 3 is 3-colorable.
O.V.Borodin and A.N.Glebov. A sufﬁcient condition for plane graphs to be 3-colorable. Diskret. analyz i issled. oper. 10, no. 3:3--11, 2004 (in Russian).

Every planar graph without cycles of length 5 and without triangles at distance less than 3 is 3-colorable.
B. Xu. A 3-color theorem on plane graphs without 5-circuits. Acta Mathematica Sinica, 23(6):1059--1062, 2006.

Planar graphs without 5-cycles and with minimum distance between triangles at least two are 3-colorable.
O.V. Borodin and A.N. Glebov. Planar graphs without 5-cycles and with minimum distance between triangles at least two are 3-colorable. In Journal of Graph Theory (to appear), 2009.

Every planar graph without cycles of length 5,7 and without adjacent triangles is 3-colorable.
B. Xu.On 3-colorable plane graphs without 5- and 7-cycles. Journal of Combinatorial Theory, Series B, 96:958--963, 2006.
See: http://arxiv.org/abs/0810.1437
O.V. Borodin, A.N. Glebov, M. Montassier, and A. Raspaud. Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable. In Journal of Combinatorial Theory, Series B, 99:668--673, 2009.

Every planar graph without 4-, 5-, and 7-cycles and without intersecting triangles is 3-colorable.
B. Xu. On 3-coloring of plane graphs. Acta Math. Appl. Sinica 20:597--604, 2004.

Every planar graph without triangles adjacent to cycles of lengths 3 to 9 is 3-colorable.
O.V. Borodin, A.N. Glebov, T.R. Jensen, and A. Raspaud. Planar graphs without triangles adjacent to cycles of length from 3 to 9 are 3-colorable. Sib. Elec. Math. Rep. 3:428--440, 2006.

Planar graphs without adjacent cycles of length at most seven are 3-colorable.
O.V. Borodin, M. Montassier, and A. Raspaud. Planar graphs without adjacent cycles of length at most seven are 3-colorable. In Discrete Mathematics, 310(1):167--173, 2010.

Every planar graph without triangles adjacent to cycles of lengths 4 to 7 is 3-colorable.
O.V. Borodin, A.N. Glebov, and A. Raspaud. Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable. Manuscript, 2009.

Every planar graph without cycles of lengths 4 and 5 and without triangles at distance less than 4 is 3-choosable.
M. Montassier, A. Raspaud, and W. Wang. Bordeaux 3-Color Conjecture and 3-choosability. Discrete Mathematics, 306:573--579, 2006.

Every planar graph without cycles of lengths 4,5,6 and without triangles at distance less than 3 is 3-choosable.
M. Montassier, A. Raspaud, and W. Wang. Bordeaux 3-Color Conjecture and 3-choosability. Discrete Mathematics, 306:573--579, 2006.

Every planar graph without cycles of lengths 5,6,7 and without triangles at distance less than 3 is 3-choosable.
H. Zhang, Z. Sun. On 3-choosability of planar graphs without certain cycles. Information Processing Letters, 107:102-106, 2008.

Every planar graph without cycles of lengths 5,6,8 and without triangles at distance less than 2 is 3-choosable.
H. Zhang, Z. Sun. On 3-choosability of planar graphs without certain cycles. Information Processing Letters, 107:102-106, 2008.

There exists a not 3-choosable planar graph without 4-,5-cycles and intersecting triangles having 380 vertices.
D.-Q. Wang, Y.-P. Wen, and K.-L. Wang. A smaller planar graph without 4-,5-cycles and intersecting triangles that is not 3-choosable. Information Processing Letters, in press, 2008.

Every planar graph with (1) no triangles, (2) no intersecting 4-cycles, (3) no 5-cycles intersecting 4-cycles, is 3-choosable.
X. Li. On 3-choosable planar graphs of girth at least 4. Discrete Mathematics, in press, 2008.

Every triangle-free planar graph without 4-cycles adjacent to 4- and 5-cycles is 3-choosable.
Z. Dvorak, B. Lidicky, R. Skrekovski. 3-choosability of triangle-free planar graphs with constraint on 4-cycles. Maunscript 2008.

In Havel's Problem, C exists.
Z. Dvorak, D. Kral, and R. Thomas. Coloring planar graphs with triangles far apart. Manuscript, 2009.

Every planar graph without 3-cycles at distance less than 4 and without triangular 5-cycles is 3-colorable.
O.V. Borodin, A.N. Glebov, and T.R. Jensen. A step towards Havel's 3 Color Conjecture. Manuscript, 2009.

If G is a planar graph such that the distance between each pair of (≤4)-cycles is at least 26, then G is 3-choosable.
Z. Dvorak. 3-choosability of planar graphs with (≤4)-cycles far apart. Manuscript, 2011.
http://arxiv.org/abs/1101.4275v1

Open Problems & Conjectures

Steinberg's Conjecture '76 : Every planar graph without cycles of lengths 4 and 5 is 3-colorable.

R. Steinberg. The state of the three color problem. Quo Vadis, Graph Theory?, Ann. Discrete Math. 55:211--248, 1993.

Havel's Problem '69 : Does there exist a constant C such that every planar graph with the minimal distance between triangles at least C is 3-colorable?

I.Havel. On a conjecture of Grünbaum. Journal of Combinatorial Theory, Serie B, 7:184--186, 1969.
O zbarvitelnosti rovinnych grafu theremi barvami. Math. Geometrie a theorie grafu (Praha), 89--91, 1970.

The answer is YES: Coloring planar graphs with triangles far apart. Z. Dvorak, D. Kral, and R. Thomas. Manuscript, 2009.

Strong Bordeaux Conjecture '03 : Every planar graph without 5-cycle and without adjacent triangle is 3-colorable.

O.V. Borodin and A. Raspaud. A sufficient condition for a planar graph to be 3-colorable. Journal of Combinatorial Theory, Serie B, 88:17--27, 2003.

Novosibirsk 3-Color Conjecture '06 : Every planar graph without 3-cycles adjacent to cycles of length 3 or 5 is 3-colorable.

O.V. Borodin, A.N. Glebov, T.R. Jensen, and A. Raspaud. Planar graphs without triangles adjacent to cycles of length from 3 to 9 are 3-colorable. Sib. Elec. Math. Rep. 3:428--440, 2006.

Acknowledgments

Thanks to Zdenek Dvorak, Bernard Lidicky.