Article ID Journal Published Year Pages File Type
4647534 Discrete Mathematics 2014 14 Pages PDF
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
, , ,