Title of article :
Acyclic improper choosability of graphs
Author/Authors :
Esperet، نويسنده , , Louis and Pinlou، نويسنده , , Alexandre، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2007
Pages :
8
From page :
251
To page :
258
Abstract :
We consider improper colorings (sometimes called generalized, defective or relaxed colorings) in which every color class has a bounded degree. We propose a natural extension of improper colorings: acyclic improper choosability. We prove that subcubic graphs are acyclically (3, 1)*-choosable (i.e. they are acyclically 3-choosable with color classes of maximum degree one). Using a linear time algorithm, we also prove that outerplanar graphs are acyclically (2, 5)*-choosable (i.e. they are acyclically 2-choosable with color classes of maximum degree five). Both results are optimal. We finally prove that acyclic choosability and acyclic improper choosability of planar graphs are equivalent notions.
Keywords :
Improper coloring , Acyclic coloring , Choosability , cubic graphs , Outerplanar graphs
Journal title :
Electronic Notes in Discrete Mathematics
Serial Year :
2007
Journal title :
Electronic Notes in Discrete Mathematics
Record number :
1454581
Link To Document :
بازگشت