Title of article :
On acyclic 4-choosability of planar graphs without short cycles
Author/Authors :
Chen، نويسنده , , Min and Raspaud، نويسنده , , André، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2010
Abstract :
Let G = ( V , E ) be a graph. A proper vertex coloring of G is acyclic if G contains no bicolored cycle. Namely, every cycle of G must be colored with at least three colors. G is acyclically L -list colorable if for a given list assignment L = { L ( v ) : v ∈ V } , 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.
s paper, we prove that planar graphs with neither { 4 , 5 } -cycles nor 8-cycles having a triangular chord are acyclically 4-choosable. This implies that planar graphs either without { 4 , 5 , 7 } -cycles or without { 4 , 5 , 8 } -cycles are acyclically 4-choosable.
Keywords :
Acyclic colorings , Choosable , cycle , Planar graphs
Journal title :
Discrete Mathematics
Journal title :
Discrete Mathematics