• 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