2-Distance Coloring of Sparse Graphs

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, that is, the problem of coloring the vertices while ensuring that two vertices that are adjacent or have a common neighbor receive different colors. We prove that graphs with maximum average degree less than inline image and maximum degree Δ at least 4 are 2-distance inline image-colorable, which is optimal and improves previous results from Dolama and Sopena, and from Borodin et al. We also prove that graphs with maximum average degree less than inline image (resp. inline image, inline image) and maximum degree Δ at least 5 (resp. 6, 8) are list 2-distance inline image-colorable, which improves previous results from Borodin et al., and from Ivanova. We prove that any graph with maximum average degree m less than inline image and with large enough maximum degree Δ (depending only on m) can be list 2-distance inline image-colored. There exist graphs with arbitrarily large maximum degree and maximum average degree less than 3 that cannot be 2-distance inline image-colored: the question of what happens between inline image and 3 remains open. We prove also that any graph with maximum average degree inline image can be list 2-distance inline image-colored (C depending only on m). It is optimal as there exist graphs with arbitrarily large maximum degree and maximum average degree less than 4 that cannot be 2-distance colored with less than inline image colors. Most of the above results can be transposed to injective list coloring with one color less.
Type de document :
Article dans une revue
Journal of Graph Theory, Wiley, 2014, 77 (3), pp.190-218. 〈10.1002/jgt.21782〉
Liste complète des métadonnées

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

Identifiants

Collections

Citation

Marthe Bonamy, Benjamin Lévêque, Alexandre Pinlou. 2-Distance Coloring of Sparse Graphs. Journal of Graph Theory, Wiley, 2014, 77 (3), pp.190-218. 〈10.1002/jgt.21782〉. 〈lirmm-01233451〉

Partager

Métriques

Consultations de la notice

85