A sufficient condition for planar graphs to be acyclically 5-choosable

✍ Scribed by Min Chen; André Raspaud

• Publisher: John Wiley and Sons
• Year: 2011
• Tongue: English
• Weight: 216 KB
• Volume: 70
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20604

✦ Synopsis

Abstract

A proper vertex coloring of a graph G = (V, E) is acyclic if G contains no bicolored cycle. Given a list assignment L = {L(v)|v∈V} of G, we say G is acyclically L‐list colorable if there exists a proper acyclic coloring π of G such that π(v)∈L(v) for all v∈V. If G is acyclically L‐list colorable for any list assignment with |L(v)|≥k for all v∈V, then G is acyclically k‐choosable. In this article we prove that every planar graph without 4‐cycles and without intersecting triangles is acyclically 5‐choosable. This improves the result in [M. Chen and W. Wang, Discrete Math 308 (2008), 6216–6225], which says that every planar graph without 4‐cycles and without two triangles at distance less than 3 is acyclically 5‐choosable. © 2011 Wiley Periodicals, Inc. J Graph Theory