Acyclic 3-choosability of sparse graphs with girth at least 7.

*(English)*Zbl 1213.05049Summary: Every planar graph is known to be acyclically 7-choosable and is conjectured to be acyclically 5-choosable [O.V. Borodin, D. G. Fon-Der-Flaas, A. Kostocha, A. Raspaud and E. Sopena, J. Graph Theory 40, No.2, 83–90 (2002; Zbl 1004.05029)]. This conjecture, if proved, would imply both Borodin’s acyclic 5-color theorem [O. V. Borodin, Discrete Math. 25, 211–236 (1979; Zbl 0406.05031)] and Thomassen’s 5-choosability theorem [C. Thomassen, J. Comb. Theory, Ser. B 62, No.1, 180-181 (1994; Zbl 0805.05023)]. However, as yet it has been verified only for several restricted classes of graphs. Some sufficient conditions have also been obtained for a planar graph to be acyclically 4- and 3-choosable.

We prove that each planar graph of girth at least 7 is acyclically 3-choosable. This is a common strengthening of the facts that such a graph is acyclically 3-colorable and that a planar graph of girth at least 8 is acyclically 3-choosable. More generally, we prove that every graph with girth at least 7 and maximum average degree less than \(\frac{14}5\) is acyclically 3-choosable.

We prove that each planar graph of girth at least 7 is acyclically 3-choosable. This is a common strengthening of the facts that such a graph is acyclically 3-colorable and that a planar graph of girth at least 8 is acyclically 3-choosable. More generally, we prove that every graph with girth at least 7 and maximum average degree less than \(\frac{14}5\) is acyclically 3-choosable.

##### MSC:

05C10 | Planar graphs; geometric and topological aspects of graph theory |

05C15 | Coloring of graphs and hypergraphs |

PDF
BibTeX
XML
Cite

\textit{O. V. Borodin} et al., Discrete Math. 310, No. 17--18, 2426--2434 (2010; Zbl 1213.05049)

Full Text:
DOI

##### References:

[1] | Borodin, O.V., On acyclic colorings of planar graphs, Discrete math., 25, 211-236, (1979) · Zbl 0406.05031 |

[2] | Borodin, O.V., Acyclic 3-choosability of planar graphs without cycles of length from 4 to 12, Diskretn. anal. issled. oper. ser. 1, 16, 5, 26-33, (2009), (in Russian) · Zbl 1249.05107 |

[3] | Borodin, O.V., Acyclic 4-colorability of planar graphs without 4- and 6-cycles, Diskretn. anal. issled. oper. ser. 1, 16, 6, 3-11, (2009) · Zbl 1249.05108 |

[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, 83-90, (2002) · Zbl 1004.05029 |

[5] | Borodin, O.V.; Ivanova, A.O., Oriented 7-coloring of plane graphs with girth at least 7, Sib. electron. math. rep., 2, 222-229, (2005) · Zbl 1095.05013 |

[6] | O.V. Borodin, A.O. Ivanova, Acyclic 3-choosability of planar graphs with no cycles of length from 4 to 11 (submitted for publication). · Zbl 1329.05101 |

[7] | O.V. Borodin, A.O. Ivanova, Acyclic 5-choosability of planar graphs without adjacent short cycles (submitted for publication). · Zbl 1235.05038 |

[8] | O.V. Borodin, A.O. Ivanova, List strong linear 2-arboricity of sparse graphs, J. Graph Theory, in press (doi:10.1002/jgt20516). · Zbl 1218.05038 |

[9] | O.V. Borodin, A.O. Ivanova, A. Raspaud, Acyclic 4-choosability of planar graphs with neither 4-cycles nor triangular 6-cycles (submitted for publication). · Zbl 1209.05063 |

[10] | Borodin, O.V.; Kostochka, A.V.; Woodall, D.R., Acyclic colorings of planar graphs with large girth, J. lond. math. soc., 60, 344-352, (1999) · Zbl 0940.05032 |

[11] | M. Chen, A. Raspaud, W. Wang, Acyclic 4-choosability of planar graphs without prescribed cycles (submitted for publication). · Zbl 1221.05075 |

[12] | Chen, M.; Wang, W., Acyclic 5-choosability of planar graphs without 4-cycles, Discrete math., 308, 6216-6225, (2008) · Zbl 1189.05059 |

[13] | Grünbaum, B., Acyclic colorings of planar graphs, Israel J. math., 14, 3, 390-408, (1973) · Zbl 0265.05103 |

[14] | Hell, P.; Nešetřil, J., () |

[15] | Hocquard, H.; Montassier, M., Every planar graph without cycles of lengths 4 to 12 is acyclically 3-choosable, Inform. process. lett., 109, 21-22, 1193-1196, (2009) · Zbl 1197.05050 |

[16] | Jensen, T.R.; Toft, B., Graph coloring problems, (1995), Wiley Interscience · Zbl 0971.05046 |

[17] | Kostochka, A.V.; Mel’nikov, L.S., Note to the paper of grünbaum on acyclic colorings, Discrete math., 14, 403-406, (1976) · Zbl 0318.05103 |

[18] | Montassier, M., Acyclic 4-choosability of planar graphs with girth at least 5, Graph theory trends math., 299-310, (2006) · Zbl 1118.05036 |

[19] | Montassier, M.; Ochem, P.; Raspaud, A., On the acyclic choosability of graphs, J. graph theory, 51, 281-300, (2006) · Zbl 1107.05036 |

[20] | Montassier, M.; Raspaud, A.; Wang, W., Acyclic 4-choosability of planar graphs without cycles of specific lengths, Algorithms combin., 26, 473-491, (2006) · Zbl 1120.05034 |

[21] | Montassier, M.; Raspaud, A.; Wang, W., Acyclic 5-choosability of planar graphs without small cycles, J. graph theory, 54, 245-260, (2007) · Zbl 1114.05037 |

[22] | Thomassen, C., Every planar graph is 5-choosable, J. combin. theory ser. B, 62, 180-181, (1994) · Zbl 0805.05023 |

[23] | Thomassen, C., 3-List-coloring planar graphs of girth 5, J. combin. theory ser. B, 64, 101-107, (1995) · Zbl 0822.05029 |

[24] | Voigt, M., List colorings of planar graph, Discrete math., 120, 215-219, (1993) · Zbl 0790.05030 |

[25] | Voigt, M., A not 3-choosable planar graph without 3-cycles, Discrete math., 146, 325-328, (1995) · Zbl 0843.05034 |

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.