Acyclic 3-choosability of plane graphs without cycles of length from~4 to~12

O. V. Borodin

Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 5, pp. 26-33.

Résumé

Every planar graph is known to be acyclically 7-choosable and is conjectured to be acyclically 5-choosable (Borodin et al., 2002). This conjecture, if proved, would imply both Borodin's acyclic 5-color theorem (1979) and Thomassen's 5-choosability theorem (1994). However, as yet it has been verified only for several restricted classes of graphs. Some sufficient conditions are also obtained for a planar graph to be acyclically 4- and 3-choosable. In particular, a planar graph of girth at least 7 is acyclically 3-colorable (Borodin, Kostochka, and Woodall, 1999) and acyclically 3-choosable (Borodin et al., 2009). A natural measure of sparseness, introduced by Erdős and Steinberg, is the absence of $k$-cycles, where $4\le k\le S$. Here, we prove that every planar graph with no cycles with length from 4 to 12 is acyclically 3-choosable. Bibl. 18.

Détail

Mots-clés : planar graph, acyclic coloring, acyclic choosability.

Bibliographie

[1] Borodin O. V., “On acyclic colorings of planar graphs”, Discrete Math., 25 (1979), 211–236 | DOI | MR | Zbl

[2] Borodin O. V., “Structural properties of plane graphs without adjacent triangles and an application to 3-colorings”, J. 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

[3] Borodin O. V., Kostochka A. V., Woodall D. R., “Acyclic colorings of planar graphs with large girth”, J. London Math. Soc., 60 (1999), 344–352 | DOI | MR | Zbl

[4] Borodin O. V., Fon-Der-Flaass D. G., Kostochka A. V., Raspaud A., Sopena E., “Acyclic list 7-coloring of planar graphs”, J. Graph Theory, 40 (2002), 83–90 | DOI | MR | Zbl

[5] Borodin O. V., Glebov A. N., Raspaud A., Salavatipour M. R., “Planar graphs without cycles of length from 4 to 7 are 3-colorable”, J. Combin. Theory Ser. B, 93 (2005), 303–311 | DOI | MR | Zbl

[6] Borodin O. V., Chen M., Ivanova A. O., Raspaud A., “Acyclic 3-choosability of sparse graphs with girth at least 7” (to appear)

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

[8] Grünbaum B., “Acyclic colorings of planar graphs”, Israel J. Math., 14:3 (1973), 390–408 | DOI | MR | Zbl

[9] Hell P., Nešetřil J., Graphs and homomorphisms, Oxford Lect. Series in Mathematics and its Applications, 28, Oxford Univ. Press, Oxford, 2004, xii+244 pp. | MR | Zbl

[10] Jensen T. R., Toft B., Graph coloring problems, A Wiley-Interscience Publ., John Wiley Sons Inc., New York, 1995, xxii+295 pp. | MR | Zbl

[11] Kostochka A. V., Mel'nikov L. S., “Note to the paper of Grünbaum on acyclic colorings”, Discrete Math., 14 (1976), 403–406 | DOI | MR | Zbl

[12] Montassier M., “Acyclic 4-choosability of planar graphs with girth at least 5”, Graph Theory Trends in Mathematics, Birkhäuser, Basel, 2006, 299–310 | MR

[13] Montassier M., Ochem P., Raspaud A., “On the acyclic choosability of graphs”, J. Graph Theory, 51 (2006), 281–300 | DOI | MR | Zbl

[14] Steinberg R., “The state of the three color problem”, Ann. Discrete Math., 55 (1993), 211–248 | DOI | MR | Zbl

[15] Thomassen C., “Every planar graph is 5-choosable”, J. Combin. Theory Ser. B, 62 (1994), 180–181 | DOI | MR | Zbl

[16] Thomassen C., “3-List-coloring planar graphs of girth 5”, J. Combin. Theory Ser. B, 64 (1995), 101–107 | DOI | MR | Zbl

[17] Voigt M., “List colorings of planar graph”, Discrete Math., 120 (1993), 215–219 | DOI | MR | Zbl

[18] Voigt M., “A not 3-choosable planar graph without 3-cycles”, Discrete Math., 146 (1995), 325–328 | DOI | MR | Zbl