Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647534 | Discrete Mathematics | 2014 | 14 Pages |
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 66 and of maximum degree ΔΔ are list 2-distance (Δ+2)(Δ+2)-colorable when Δ≥24Δ≥24 (Borodin and Ivanova (2009)) and 2-distance (Δ+2)(Δ+2)-colorable when Δ≥18Δ≥18 (Borodin and Ivanova (2009)). We prove here that Δ≥17Δ≥17 suffices in both cases. More generally, we show that graphs with maximum average degree less than 33 and Δ≥17Δ≥17 are list 2-distance (Δ+2)(Δ+2)-colorable. The proof can be transposed to list injective (Δ+1)(Δ+1)-coloring.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Marthe Bonamy, Benjamin Lévêque, Alexandre Pinlou,