Acyclic $3$-choosability of planar graphs with no cycles of length from~$4$ to~$11$

O. V. Borodin ; A. O. Ivanova

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 7 (2010), pp. 275-283.

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., 2010). A natural measure of sparseness, introduced by Erdős and Steinberg, is the absence of $k$-cycles, where $4\le k\le C$. Here, we prove that every planar graph with no cycles of length from $4$ to $11$ is acyclically $3$-choosable.

Détail

Keywords: acyclic coloring, planar graph, forbidden cycles.

Bibliographie

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

[2] O. V. Borodin, “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] O. V. Borodin, “Acyclically 4-colorable planar graphs without 4- and 6-cycles”, Diskretn. Anal. Issled. Oper., 16:6 (2009), 3–11 (in Russian) | MR

[4] O. V. Borodin, “Acyclic 4-colorability of planar graphs without 4- and 5-cycles”, Diskretn. Anal. Issled. Oper., 17:2 (2010), 20–38 (in Russian) | MR

[5] O. V. Borodin, “Acyclic 3-choosability of planar graphs without cycles of length from 4 to 12”, Diskretn. Anal. Issled. Oper., 16:5 (2009), 26–33 (in Russian) | MR

[6] O. V. Borodin, M. Chen, A. O. Ivanova, and A. Raspaud, “Acyclic 3-choosability of sparse graphs with girth at least 7”, Discrete Math., 310:17–18 (2010), 2426–2434 | DOI | MR | Zbl

[7] O. V. Borodin, A. V. Kostochka, J. Nesetril, A. Raspaud, and E. Sopena, “On the maximal average degree and the oriented chromatic number of a graph”, Discrete Math., 206 (1999), 77–89 | DOI | MR | Zbl

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

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

[10] O. V. Borodin, A. O. Ivanova, and A. Raspaud, “Acyclic 4-choosability of planar graphs with neither 4-cycles nor triangular 6-cycles”, Discrete Math., 310 (2010), 2946–2950 | DOI | Zbl

[11] O. V. Borodin, S. J. Kim, A. V. Kostochka, and D. B. West, “Homomorphisms of sparse graphs with large girth”, J. Combin. Theory B, 90 (2004), 147–159 | DOI | MR | Zbl

[12] 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”, J. Combin. Theory Ser. B, 93 (2005), 303–311 | DOI | MR | Zbl

[13] O. V. Borodin, A. O. Ivanova, and A. V. Kostochka, “Oriented vertex 5-coloring of sparse graphs”, Diskretn. Anal. Issled. Oper. Ser. 1, 13:1 (2006), 16–32 (in Russian) | MR

[14] O. V. Borodin, S. G. Hartke, A. O. Ivanova, A. V. Kostochka, and D. B. West, “$(5,2)$-Coloring of Sparse Graphs”, Sib. Elektron. Mat. Izv., 5 (2008), 417–426 | MR

[15] M. Chen and A. Raspaud, Planar graphs without 4-, 5-, and 8-cycles are acyclically 4-choosable, submitted

[16] M. Chen, A. Raspaud and W. Wang, Acyclic 4-choosability of planar graphs without prescribed cycles, submitted

[17] P. Hell and J. Nešetřil, Graphs and homomorphisms, Oxford Lecture Series in Mathematics and its Applications, 28, Oxford University Press, Oxford, 2004 | MR | Zbl

[18] H. Hocquard and M. Montassier, “Every planar graph without cycles of lengths 4 to 12 is acyclically 3-choosable”, Information Processing Letters, 109 (2009), 21–22 ; 1193–1196 | DOI | MR | Zbl

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

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

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

[22] M. Montassier, “Acyclic 4-choosability of Planar Graphs with Girth at Least 5”, Graph theory in Paris, Trends Math., 2006, 299–310 | MR

[23] M. Montassier, A. Raspaud, W. Wang, “Acyclic 4-choosability of planar graphs without cycles of specific lengths”, Topics in discrete mathematics, Algorithms Combin., 26, Springer, Berlin, 2006, 473–491 | MR | Zbl

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

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

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

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

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

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

[30] M. Voigt, R. Steinberg, “A non-3-choosable planar graph without cycles of length 4 and 5”, Discrete Math., 307:7–8 (2007), 1013–1015 | DOI | MR | Zbl