×

zbMATH — the first resource for mathematics

Acyclic 4-choosability of planar graphs with no 4- and 5-cycles. (English) Zbl 1261.05013
Summary: Every planar graph is known to be acyclically 7-choosable and is conjectured to be acyclically 5-choosable [O. V. Borodin et al., J. Graph Theory 40, No. 2, 83–90 (2002; Zbl 1004.05029)]. This conjecture if proved would imply both O. V. Borodin’s [Discrete Math. 25, 211–236 (1979; Zbl 0406.05031)] acyclic 5-color theorem and C. Thomassen’s [J. Comb. Theory, Ser. B 62, No. 1, 180–181 (1994; Zbl 0805.05023)] 5-choosability theorem. 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, the acyclic 4-choosability was proved for the following planar graphs: without 3-, 4-, and 5-cycles [M. Montassier et al., J. Graph Theory 51, No. 4, 281–300 (2006; Zbl 1107.05036)], without 4-, 5-, and 6-cycles, or without 4-, 5-, and 7-cycles, or without 4-, 5-, and intersecting 3-cycles [M. Montassier et al., Algorithms and Combinatorics 26, 473–491 (2006; Zbl 1120.05034)], and neither 4- and 5-cycles nor 8-cycles having a triangular chord [M. Chen and A. Raspaud, Discrete Math. 310, No. 15–16, 2113–2118 (2010)].
The purpose of this paper is to strengthen these results by proving that each planar graph without 4- and 5-cycles is acyclically 4-choosable.

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abbott, On small faces in 4-critical graphs, Ars Combinatoria 32 pp 203– (1991) · Zbl 0755.05062
[2] Albertson, Every planar graph has an acyclic 7-coloring, Israel J Math 28 pp 169– (1977) · Zbl 0374.05022 · doi:10.1007/BF02759792
[3] Borodin, Proof of B. Grunbaum’s conjecture on the acyclic 5-colorability of planar graphs, Dokl Akad Nauk SSSR 231 (1) pp 18– (1976) · Zbl 0363.05031
[4] Borodin, On acyclic colorings of planar graphs, Discrete Math 25 pp 211– (1979) · Zbl 0406.05031 · doi:10.1016/0012-365X(79)90077-3
[5] Borodin, Structural properties of plane graphs without adjacent triangles and an application to 3-colorings, J Graph Theory 21 (2) pp 183– (1996) · Zbl 0838.05039 · doi:10.1002/(SICI)1097-0118(199602)21:2<183::AID-JGT7>3.0.CO;2-N
[6] Borodin, Acyclic 3-choosability of planar graphs with no cycles with length from 4 to 12, Diskretn Anal Issled Oper 16 (5) pp 26– (2009) · Zbl 1249.05107
[7] Borodin, Acyclic 4-colorability of planar graphs without 4- and 6-cycles, Diskretn Anal Issled Oper 16 (6) pp 3– (2009) · Zbl 1249.05108
[8] Borodin, Acyclic 4-colorability of planar graphs with neither 4-cycles nor 5-cycles, Diskretn Anal Issled Oper 17 (2) pp 20– (2010) · Zbl 1209.05063
[9] Borodin, Acyclic 3-choosability of sparse graphs with girth at least 7, Discrete Math 310 (17-18) pp 2426– (2010) · Zbl 1213.05049 · doi:10.1016/j.disc.2010.05.032
[10] Borodin, Acyclic list 7-coloring of planar graphs, J Graph Theory 40 pp 83– (2002) · Zbl 1004.05029 · doi:10.1002/jgt.10035
[11] Borodin, Planar graphs without cycles of length from 4 to 7 are 3-colorable, J Combin Theory Ser B 93 pp 303– (2005) · Zbl 1056.05052 · doi:10.1016/j.jctb.2004.11.001
[12] Borodin, Acyclic 5-choosability of planar graphs without adjacent short cycles, J Graph Theory 68 (2) pp 169– (2011) · Zbl 1235.05038 · doi:10.1002/jgt.20549
[13] O. V. Borodin A. O. Ivanova Acyclic 4-choosability of planar graphs without adjacent short cycles (submitted) · Zbl 1252.05041
[14] Borodin, Acyclic 5-choosability of planar graphs without 4-cycles (in Russian), Sibirsk Mat Zh 52 (3) pp 522– (2011) · Zbl 1294.05057
[15] Borodin, Acyclic 3-choosability of planar graphs with no cycles of length from 4 to 11, Sib Elektron Mat Izv 7 pp 275– (2010) · Zbl 1329.05101
[16] Borodin, Acyclic 4-choosability of planar graphs with neither 4-cycles nor triangular 6-cycles, Discrete Math 310 (21) pp 2946– (2010) · Zbl 1209.05063 · doi:10.1016/j.disc.2010.07.001
[17] Borodin, Acyclic colorings of planar graphs with large girth, J London Math Soc 60 pp 344– (1999) · Zbl 0940.05032 · doi:10.1112/S0024610799007942
[18] Chen, On acyclic 4-choosability of planar graphs without short cycles, Discrete Math 310 (15-16) pp 2113– (2010) · Zbl 1221.05075 · doi:10.1016/j.disc.2010.03.036
[19] M. Chen A. Raspaud A sufficient condition for planar graphs to be acyclically 5-choosable (submitted)
[20] M. Chen A. Raspaud Planar graphs without 4- and 5-cycles are acyclically 4-choosable (submitted)
[21] Chen, Acyclic 5-choosability of planar graphs without 4-cycles, Discrete Math 308 pp 6216– (2008) · Zbl 1189.05059 · doi:10.1016/j.disc.2007.11.076
[22] M. Chen A. Raspaud W. Wang Acyclic 4-choosability of planar graphs without prescribed cycles (submitted) · Zbl 1221.05075
[23] Grünbaum, Acyclic colorings of planar graphs, Israel J Math 14 (3) pp 390– (1973) · Zbl 0265.05103 · doi:10.1007/BF02764716
[24] Hell, Graphs and homomorphisms, oxford lecture series in mathematics and its applications 28 (2004)
[25] Hocquard, Every planar graph without cycles of lengths 4 to 12 is acyclically 3-choosable, Inform Process Lett 109 (21-22) pp 1193– (2009) · Zbl 1197.05050 · doi:10.1016/j.ipl.2009.08.004
[26] Jensen, Graph coloring problems (1995) · Zbl 0855.05054
[27] Kostochka, Acyclic 6-coloring of planar graphs, Diskret Analiz 28 pp 40– (1976) · Zbl 0412.05043
[28] Kostochka, Note to the paper of Grünbaum on acyclic colorings, Discrete Math 14 pp 403– (1976) · Zbl 0318.05103 · doi:10.1016/0012-365X(76)90075-3
[29] Lam, The 4-choosability of plane graphs without 4-cycles, J Combin Theory Ser B 76 (1) pp 117– (1999) · Zbl 0931.05036 · doi:10.1006/jctb.1998.1893
[30] Mitchem, Every planar graph has an acyclic 8-coloring, Duke Math J 14 pp 177– (1974) · Zbl 0284.05103 · doi:10.1215/S0012-7094-74-04119-2
[31] Montassier, Acyclic 4-choosability of planar graphs with girth at least 5, Graph Theory Trends Math pp 299– (2006)
[32] Montassier, On the acyclic choosability of graphs, J Graph Theory 51 pp 281– (2006) · Zbl 1107.05036 · doi:10.1002/jgt.20134
[33] Montassier, Topics Discrete Math pp 473– (2006) · doi:10.1007/3-540-33700-8_23
[34] Montassier, Acyclic 5-choosability of planar graphs without small cycles, J Graph Theory 54 pp 245– (2007) · Zbl 1114.05037 · doi:10.1002/jgt.20206
[35] Steinberg, The state of the three color problem, Quo Vadis, Graph Theory? J. Gimbel, J. W. Kennedy, and L. V. Quintas (eds.), Ann Discrete Math 55 pp 211– (1993) · doi:10.1016/S0167-5060(08)70391-1
[36] Thomassen, Every planar graph is 5-choosable, J Combin Theory Ser B 62 pp 180– (1994) · Zbl 0805.05023 · doi:10.1006/jctb.1994.1062
[37] Thomassen, 3-list-coloring planar graphs of girth 5, J Combin Theory Ser B 64 pp 101– (1995) · Zbl 0822.05029 · doi:10.1006/jctb.1995.1027
[38] Voigt, List colorings of planar graph, Discrete Math 120 pp 215– (1993) · Zbl 0790.05030 · doi:10.1016/0012-365X(93)90579-I
[39] Voigt, A not 3-choosable planar graph without 3-cycles, Discrete Math 146 pp 325– (1995) · Zbl 0843.05034 · doi:10.1016/0012-365X(94)00180-9
[40] Voigt, A non-3-choosable planar graph without cycles of length 4 and 5, Discrete Math 307 (7-8) pp 1013– (2007) · Zbl 1112.05041 · doi:10.1016/j.disc.2005.11.041
[41] Wang, Planar graphs without 4-cycles are acyclically 6-choosable, J Graph Theory 61 pp 307– (2009) · Zbl 1185.05068 · doi:10.1002/jgt.20381
[42] Zhang, Acyclic 5-choosable planar graphs with neither 4-cycles nor chordal 6-cycles, Discrete Math 309 (20) pp 6087– (2009) · Zbl 1204.05049 · doi:10.1016/j.disc.2009.05.018
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.