pith. sign in

Graphs with maximum degree D at least 17 and maximum average degree less than 3 are list 2-distance (D+2)-colorable

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
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 D are list 2-distance (D+2)-colorable when D>=24 (Borodin and Ivanova (2009)) and 2-distance (D+2)-colorable when D>=18 (Borodin and Ivanova (2009)). We prove here that D>=17 suffices in both cases. More generally, we show that graphs with maximum average degree less than 3 and D>=17 are list 2-distance (D+2)-colorable. The proof can be transposed to list injective (D+1)-coloring.

citation-role summary

background 1

citation-polarity summary

fields

math.CO 1

years

2022 1

verdicts

unreviewed 1

roles

background 1

polarities

background 1

representative citing papers

citing papers explorer

Showing 1 of 1 citing paper.