2-distance (\Delta+2)-coloring of sparse graphs

arXiv2109.11927MaRDI QIDQ6378484FDOQ6378484

Authors: Hoang La, Mickaël Montassier 

Publication date: 24 September 2021

Abstract: 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 $frac83$ (resp. $frac145$) and maximum degree $Deltageq6$ (resp. $Deltageq10$). As a corollary, every planar graph with girth at least $8$ (resp. $7$) and maximum degree $Deltageq6$ (resp. $Deltageq10$) admits a $2$-distance $(Delta+2)$-coloring.

This page was built for publication: $2$-distance $(\Delta+2)$-coloring of sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6378484)