Site.ThreeColorProblem History

Hide minor edits - Show changes to markup

January 26, 2011, at 07:40 AM by 147.210.129.153 -
Changed line 24 from:

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

to:

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

January 25, 2011, at 03:21 PM by 147.210.129.153 -
Changed lines 61-62 from:

Z. Dvorak, K.I. Kawarabayashi. Choosability of planar graphs with girth 5. Manuscript, 2010. [http://www.google.fr/url?sa=t&source=web&cd=3&ved=0CC8QFjAC&url=http%3A%2F%2Fiti.mff.cuni.cz%2Fseries%2Ffiles%2F2010%2Fiti490.pdf&rct=j&q=dvorak%20kawarabayashi%20choosability%20of%20planar%20graphs%20of%20girth%205&ei=Its-TamqAs238gP1hrycCA&usg=AFQjCNFILAJCeVRIvG3g84ZRiEHQnaXIGg&sig2=D-bmMZiIGsKmORA-rV-xIQ&cad=rja|(here)]

to:

Z. Dvorak, K.I. Kawarabayashi. Choosability of planar graphs with girth 5. Manuscript, 2010. (here)

January 25, 2011, at 03:21 PM by 147.210.129.153 -
Changed lines 58-63 from:

Every planar graphs with at most three 3-cycles is 3-colorable.\\

to:

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. [http://www.google.fr/url?sa=t&source=web&cd=3&ved=0CC8QFjAC&url=http%3A%2F%2Fiti.mff.cuni.cz%2Fseries%2Ffiles%2F2010%2Fiti490.pdf&rct=j&q=dvorak%20kawarabayashi%20choosability%20of%20planar%20graphs%20of%20girth%205&ei=Its-TamqAs238gP1hrycCA&usg=AFQjCNFILAJCeVRIvG3g84ZRiEHQnaXIGg&sig2=D-bmMZiIGsKmORA-rV-xIQ&cad=rja|(here)]

Every planar graph with at most three 3-cycles is 3-colorable.\\

January 25, 2011, at 03:15 PM by 147.210.129.153 -
Changed line 1 from:

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

to:

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

January 25, 2011, at 03:15 PM by 147.210.129.153 -
Changed line 1 from:

The 3-Color Problem

to:

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

Added line 49:

C. Thomassen. 3-list-coloring planar graphs of girth 5. J. Combin. Theory Ser. B 64(1):101--107, 1995.\\

January 25, 2011, at 03:07 PM by 147.210.129.153 -
Changed lines 210-211 from:

Z. Dvorak. 3-choosability of planar graphs with (≤4)-cycles far apart. Manuscript, 2011. http://arxiv.org/abs/1101.4275v1

to:

Z. Dvorak. 3-choosability of planar graphs with (≤4)-cycles far apart. Manuscript, 2011.
http://arxiv.org/abs/1101.4275v1

January 25, 2011, at 03:07 PM by 147.210.129.153 -
Changed lines 210-212 from:

Z. Dvorak. 3-choosability of planar graphs with (≤4)-cycles far apart. Manuscript, 2011

to:

Z. Dvorak. 3-choosability of planar graphs with (≤4)-cycles far apart. Manuscript, 2011. http://arxiv.org/abs/1101.4275v1

January 25, 2011, at 03:06 PM by 147.210.129.153 -
Added lines 209-210:

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

January 27, 2010, at 11:01 AM by 147.210.129.245 -
Added lines 53-54:

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

January 27, 2010, at 10:57 AM by 147.210.129.245 -
Added line 50:

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

January 05, 2010, at 11:11 AM by 147.210.129.245 -
Added line 49:

T.R. Jensen and C. Thomassen. The color space of a graph. Journal of Graph Theory, 34(3):234--245, 2000.\\

January 05, 2010, at 09:11 AM by 147.210.129.245 -
Changed lines 220-221 from:

I.Havel. On a conjecture of Grünbaum. Journal of Combinatorial Theory, Serie B, 7:184--186, 1969.

to:

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.

January 05, 2010, at 09:04 AM by 147.210.129.245 -
Changed line 54 from:

B. Grünbaum. Grötzsch's theorem on 3-colorings. Michigan Math. J., 10:303--310, 1963.\\

to:

B. Grünbaum. Grötzsch's theorem on 3-colorings. Michigan Math. J., 10(3):303--310, 1963.\\

January 05, 2010, at 09:02 AM by 147.210.129.245 -
Added lines 175-177:

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.

Changed line 203 from:
 O.V. Borodin, A.N. Glebov, and T.R. Jensen. A step towards Havel's 3 Color Conjecture. Manuscript 2009.
to:
 O.V. Borodin, A.N. Glebov, and T.R. Jensen. A step towards Havel's 3 Color Conjecture. Manuscript, 2009.
January 05, 2010, at 08:58 AM by 147.210.129.245 -
Changed line 199 from:

Every planar graphs without 3-cycles at distance less than 4 and without triangular 5-cycles is 3-colorable.\\

to:

Every planar graph without 3-cycles at distance less than 4 and without triangular 5-cycles is 3-colorable.\\

January 05, 2010, at 08:58 AM by 147.210.129.245 -
Added lines 198-200:

Every planar graphs 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.

January 05, 2010, at 08:53 AM by 147.210.129.245 -
Changed line 159 from:

O.V. Borodin and A.N. Glebov. Planar graphs without 5-cycles and with minimum distance between triangles at least two are 3-colorable. Manuscript, 2008.

to:

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.

January 05, 2010, at 08:52 AM by 147.210.129.245 -
January 05, 2010, at 08:50 AM by 147.210.129.245 -
Added lines 171-173:

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.

January 05, 2010, at 08:43 AM by 147.210.129.245 -
Changed lines 77-78 from:

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.To appear in Journal of Combinatorial Theory, Series B, 2008.

to:

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.

Changed line 164 from:

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. To appear in Journal of Combinatorial Theory, Series B, 2008.

to:

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.

January 04, 2010, at 09:22 PM by 82.251.233.204 -
Changed lines 48-50 from:

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

to:

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

Changed line 55 from:

V.A. Aksionov. On continuation of 3-coloring of planar graph. Diskret. Analiz. 26:3-19, 1974 (in Russian).\\

to:

V.A. Aksionov. On continuation of 3-coloring of planar graph. Diskret. Analiz. 26:3--19, 1974 (in Russian).\\

January 04, 2010, at 09:21 PM by 82.251.233.204 -
Changed lines 55-56 from:

V.A. Aksionov. On continuation of 3-coloring of planar graph. Diskret. Analiz. 26:3-19, 1974 (in Russian).

to:

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.

January 04, 2010, at 07:40 PM by 82.255.155.234 -
Changed line 146 from:

V.A. Aksionov and L.S. Mel'nikov. Some counterexamples associated with the Three Color Problem. Journal of Combinatorial Theory, Serie B, 28:1--9, 1980.

to:

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.

January 04, 2010, at 07:38 PM by 82.255.155.234 -
Added line 47:

V.A. Aksionov. Chromatic connected vertices in planar graphs. Diskret. Analiz 31:5--16, 1977 (in Russian).\\

January 04, 2010, at 07:32 PM by 82.255.155.234 -
Changed lines 9-10 from:

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

to:

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

Changed lines 13-14 from:

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?

to:

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?

Changed lines 24-25 from:

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

to:

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

Changed line 30 from:

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

to:

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

January 04, 2010, at 07:24 PM by 82.255.155.234 -
Changed line 28 from:

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:

to:

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:

November 25, 2009, at 03:27 PM by 147.210.129.245 -
Added lines 92-94:

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.

Changed line 96 from:

M. Voigt. A not 3-choosable planar graph without 3-cycles.Discrete Mathematics, 307(7-8):1013-1015, 2007.

to:

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

November 25, 2009, at 03:19 PM by 147.210.129.245 -
Changed lines 93-94 from:

M. Voigt. A not 3-choosable planar graph without 3-cycles.Discrete Mathematics, 307(7-8):1013-1015, 2007.'''

to:

M. Voigt. A not 3-choosable planar graph without 3-cycles.Discrete Mathematics, 307(7-8):1013-1015, 2007.

Changed line 204 from:

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

to:

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?\\

October 05, 2009, at 03:58 PM by 147.210.128.239 -
Changed line 225 from:

Thanks to Zdenek Dvorak, Bernard Lidicky for their informations.

to:

Thanks to Zdenek Dvorak, Bernard Lidicky.

October 05, 2009, at 03:58 PM by 147.210.128.239 -
Changed line 225 from:

Thanks to Zdenek Dvorak, Bernard Lidicky for their infomations.

to:

Thanks to Zdenek Dvorak, Bernard Lidicky for their informations.

October 05, 2009, at 03:57 PM by 147.210.128.239 -
Changed line 189 from:

Z. Dvorak, D. Kral, and R. Thomas. Coloring planar grapgs with triangles far apart. Manuscript, 2009.

to:

Z. Dvorak, D. Kral, and R. Thomas. Coloring planar graphs with triangles far apart. Manuscript, 2009.

October 05, 2009, at 03:57 PM by 147.210.128.239 -
Changed line 189 from:

Z. Dvorak, D. Kral, and R. Thomas. '''Coloring planar grapgs with triangles far apart. Manuscript, 2009.

to:

Z. Dvorak, D. Kral, and R. Thomas. Coloring planar grapgs with triangles far apart. Manuscript, 2009.

October 05, 2009, at 03:56 PM by 147.210.128.239 -
Added lines 188-190:

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

Changed lines 209-211 from:

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

to:

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

Changed line 225 from:

Thanks to Bernard Lidicky.

to:

Thanks to Zdenek Dvorak, Bernard Lidicky for their infomations.

October 05, 2009, at 03:53 PM by 147.210.128.239 -
Changed lines 15-18 from:

Aksionov and Mel'nikov proved that if C exists, then C >= 4, and conjectured that C=5. These two problems remain widely open. In 1991, 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

to:

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

Added lines 204-206:

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

August 06, 2009, at 11:35 AM by 82.64.182.115 -
Added lines 62-64:

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.

August 03, 2009, at 09:15 AM by 82.248.116.186 -
Changed line 87 from:

M. Voigt.A not 3-choosable planar graph without 3-cycles..Discrete Mathematics, 307(7-8):1013-1015, 2007'''

to:

M. Voigt. A not 3-choosable planar graph without 3-cycles.Discrete Mathematics, 307(7-8):1013-1015, 2007.'''

August 03, 2009, at 09:14 AM by 82.248.116.186 -
Added lines 85-87:

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

July 24, 2009, at 08:43 AM by 82.255.180.42 -
Added lines 151-153:

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.

March 03, 2009, at 08:22 AM by 147.210.128.239 -
Added lines 1-207:

The 3-Color Problem


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. These two problems remain widely open. In 1991, 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-cycle and without adjacent triangle 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.
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. 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.
Z. Dvorak, K-I. Kawarabayashi, R. Thomas. Three-coloring triangle-free planar graphs in linear time. Manuscript 2008.

Every planar graphs with at most three 3-cycles is 3-colorable.
B. Grünbaum. Grötzsch's theorem on 3-colorings. Michigan Math. J., 10:303--310, 1963.
V.A. Aksionov. On continuation of 3-coloring of planar graph. Diskret. Analiz. 26:3-19, 1974 (in Russian).

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 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.To appear in Journal of Combinatorial Theory, Series B, 2008.

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.

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--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 sufficient 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. Manuscript, 2008.

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. To appear in Journal of Combinatorial Theory, Series B, 2008.

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.

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.


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

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 Bernard Lidicky.


LIRMM

HAL-LIRMM

Dept. Info UM2

GT Graphes

Vertex-partitions of planar graphs

The 3-Color Problem

Around the world