×

Acyclic 5-choosability of planar graphs without small cycles. (English) Zbl 1114.05037

Summary: A proper vertex coloring of a graph \(G = (V,E)\) is acyclic if \(G\) contains no bicolored cycle. A graph \(G\) is acyclically \(L\)-list colorable if for a given list assignment \(L = \{L(v): v\in V\}\), there exists a proper acyclic coloring \(\phi\) of \(G\) such that \(\phi (v)\in L(v)\) for all \(v\in V\). If \(G\) is acyclic \(L\)-list colorable for any list assignment with \(|L(v)|\geq k\) for all \(v\in V\), then \(G\) is acyclically \(k\)-choosable. In this article, we prove that every planar graph \(G\) without 4- and 5-cycles, or without 4- and 6-cycles is acyclically 5-choosable.

MSC:

05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albertson, Israel J Math 28 pp 169– (1977)
[2] Borodin, Discrete Math 25 pp 211– (1979)
[3] Borodin, J Graph Theory 40 pp 83– (2002)
[4] Borodin, J London Math Soc 2 pp 344– (1999)
[5] Erdos, Congr Numer 26 pp 125– (1979)
[6] Grünbaum, Israel J Math 14 pp 390– (1973)
[7] Kostochka, Metody Diskret Anal 28 pp 40– (1976)
[8] Kostochka, Discrete Math 14 pp 403– (1976)
[9] Mitchem, Duke Math J 41 pp 177– (1974)
[10] Montassier, J Graph Theory 51 pp 281– (2006)
[11] Montassier, Algorithms and Combinatorics 26 pp 473– (2006)
[12] Thomassen, J Combin Theory Ser B 62 pp 180– (1994)
[13] Vizing, Metody Diskret Anal 19 pp 3– (1976)
[14] Voigt, Discrete Math 120 pp 215– (1993)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.