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
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
Journal title :
Discrete Mathematics