• Title of article

    Graphs with maximum degree and maximum average degree less than are list -distance -colorable

  • Author/Authors

    Bonamy، نويسنده , , Marthe and Lévêque، نويسنده , , Benjamin and Pinlou، نويسنده , , Alexandre، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2014
  • Pages
    14
  • From page
    19
  • To page
    32
  • Abstract
    For graphs of bounded maximum average degree, we consider the problem of 2-distance coloring. This is the problem of coloring the vertices while ensuring that two vertices that are adjacent or have a common neighbor receive different colors. It is already known that planar graphs of girth at least 6 and of maximum degree Δ are list 2-distance ( Δ + 2 ) -colorable when Δ ≥ 24 (Borodin and Ivanova (2009)) and 2-distance ( Δ + 2 ) -colorable when Δ ≥ 18 (Borodin and Ivanova (2009)). We prove here that Δ ≥ 17 suffices in both cases. More generally, we show that graphs with maximum average degree less than 3 and Δ ≥ 17 are list 2-distance ( Δ + 2 ) -colorable. The proof can be transposed to list injective ( Δ + 1 ) -coloring.
  • Keywords
    square coloring , maximum average degree , 2-distance coloring
  • Journal title
    Discrete Mathematics
  • Serial Year
    2014
  • Journal title
    Discrete Mathematics
  • Record number

    1600566