2-distance (Δ+2)-coloring of sparse graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2021

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

Xuan Hoang La
Mickaël Montassier

Résumé

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 et versions

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

Identifiants

Citer

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

Altmetric

Partager

Gmail Mastodon Facebook X LinkedIn More