A sufficient condition for planar graphs to be acyclically 5‐choosable |
| |
Authors: | Min Chen André Raspaud |
| |
Institution: | 1. Université, Labri UMR CNRS 5800, , Bordeaux I, 33405 Talence Cedex, FranceThis work was done during her stay in LaBRI when she was preparing her PhD Thesis.;2. Université, Labri UMR CNRS 5800, , Bordeaux I, 33405 Talence Cedex, France |
| |
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 |
| |
Keywords: | acyclic coloring acyclic choosability planar graph intersecting triangles |
|
|