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