2-distance (Δ+2)-coloring of sparse graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Preprints, Working Papers, ... Year : 2021

2-distance (Δ+2)-coloring of sparse graphs

Xuan Hoang La
Mickaël Montassier


A $2$-distance $k$-coloring of a graph is a proper $k$-coloring of the vertices where vertices at distance at most 2 cannot share the same color. We prove the existence of a $2$-distance ($\Delta+2$)-coloring for graphs with maximum average degree less than $\frac{8}{3}$ (resp. $\frac{14}{5}$) and maximum degree $\Delta\geq 6$ (resp. $\Delta\geq 10$). As a corollary, every planar graph with girth at least $8$ (resp. $7$) and maximum degree $\Delta\geq 6$ (resp. $\Delta\geq 10$) admits a $2$-distance $(\Delta+2)$-coloring.

Dates and versions

lirmm-04041967 , version 1 (22-03-2023)



Xuan Hoang La, Mickaël Montassier. 2-distance (Δ+2)-coloring of sparse graphs. 2021. ⟨lirmm-04041967⟩
11 View
0 Download



Gmail Facebook X LinkedIn More