Graphs with maximum degree Δ≥17 and maximum average degree less than 33 are list 22-distance (Δ+2)-colorable

Marthe Bonamy 1 Benjamin Lévêque 1 Alexandre Pinlou 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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 Δ are list 2-distance (Δ+2)-colorable when Δ≥24 (Borodin and Ivanova (2009)) and 2-distance (Δ+2)-colorable when Δ≥18 (Borodin and Ivanova (2009)). We prove here that Δ≥17 suffices in both cases. More generally, we show that graphs with maximum average degree less than 3 and Δ≥17 are list 2-distance (Δ+2)-colorable. The proof can be transposed to list injective (Δ+1)-coloring.
Type de document :
Article dans une revue
Discrete Mathematics, Elsevier, 2014, 317, pp.19-32. 〈10.1016/j.disc.2013.10.022〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01233453
Contributeur : Alexandre Pinlou <>
Soumis le : mercredi 25 novembre 2015 - 11:16:51
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

Collections

Citation

Marthe Bonamy, Benjamin Lévêque, Alexandre Pinlou. Graphs with maximum degree Δ≥17 and maximum average degree less than 33 are list 22-distance (Δ+2)-colorable. Discrete Mathematics, Elsevier, 2014, 317, pp.19-32. 〈10.1016/j.disc.2013.10.022〉. 〈lirmm-01233453〉

Partager

Métriques

Consultations de la notice

94