Article ID Journal Published Year Pages File Type
4652844 Electronic Notes in Discrete Mathematics 2007 8 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics