Geodesic
Planar graphs without triangles adjacent to cycles of length from $3$ to $9$ are $3$-colorable
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 3 (2006), pp. 428-440 
O. V. Borodin; A. N. Glebov; T. R. Jensen; A. Raspaud. Planar graphs without triangles adjacent to cycles of length from $3$ to $9$ are $3$-colorable. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 3 (2006), pp. 428-440. http://geodesic.mathdoc.fr/item/SEMR_2006_3_a27/
@article{SEMR_2006_3_a27,
     author = {O. V. Borodin and A. N. Glebov and T. R. Jensen and A. Raspaud},
     title = {Planar graphs without triangles adjacent to cycles of length from~$3$ to~$9$ are $3$-colorable},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {428--440},
     year = {2006},
     volume = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2006_3_a27/}
}
TY  - JOUR
AU  - O. V. Borodin
AU  - A. N. Glebov
AU  - T. R. Jensen
AU  - A. Raspaud
TI  - Planar graphs without triangles adjacent to cycles of length from $3$ to $9$ are $3$-colorable
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2006
SP  - 428
EP  - 440
VL  - 3
UR  - http://geodesic.mathdoc.fr/item/SEMR_2006_3_a27/
LA  - en
ID  - SEMR_2006_3_a27
ER  - 
%0 Journal Article
%A O. V. Borodin
%A A. N. Glebov
%A T. R. Jensen
%A A. Raspaud
%T Planar graphs without triangles adjacent to cycles of length from $3$ to $9$ are $3$-colorable
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2006
%P 428-440
%V 3
%U http://geodesic.mathdoc.fr/item/SEMR_2006_3_a27/
%G en
%F SEMR_2006_3_a27

Voir la notice de l'article provenant de la source Math-Net.Ru

Planar graphs without triangles adjacent to cycles of length from $3$ to $9$ are proved to be $3$-colorable, which extends Grötzsch's theorem. We conjecture that planar graphs without $3$-cycles adjacent to cycles of length $3$ or $5$ are $3$-colorable.

[1] H. L. Abbott and B. Zhou, “On small faces in 4-critical graphs”, Ars. Combin., 32 (1991), 203–207 | MR | Zbl

[2] O. V. Borodin, “To the paper of H. L. Abbott and B. Zhou on 4-critical planar graphs”, Ars Combinatoria, 43 (1996), 191–192 | MR | Zbl

[3] O. V. Borodin, “Structural properties of plane graphs without adjacent triangles and an application to 3-colorings”, J. of Graph Theory, 21:2 (1996), 183–186 | 3.0.CO;2-N class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[4] O. V. Borodin and A. Raspaud, “A Sufficient Condition for Planar Graphs to be 3-Colorable”, J. of Combin. Theory B, 88 (2003), 17–27 | DOI | MR | Zbl

[5] H. Grötzsch, “Ein Dreifarbenzatz für dreikreisfreie Netze auf der Kugel”, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, 8 (1959), 109–120 | MR

[6] T. R. Jensen and B. Toft, Graph coloring problems, Wiley Interscience, 1995 | MR

[7] D. P. Sanders and Y. Zhao, “A note on the three color problem”, Graphs and Combinatorics, 11 (1995), 91–94 | DOI | MR | Zbl

[8] R. Steinberg, “The state of the three color problem”, Quo Vadis, Graph Theory?, Annals of Discrete Math., 55, eds. J. Gimbel, J. W. Kennedy and L. V. Quintas (eds.), 1993, 211–248 | MR | Zbl