2-distance coloring of sparse graphs

Marthe Bonamy 1 Benjamin Lévêque 1, * Alexandre Pinlou 1
* Auteur correspondant
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Résumé : Une coloration à distance 2 d'un graphe est une coloration des sommets de façon à ce que deux sommets à distance au plus deux reçoivent des couleurs différentes. On prouve que chaque graphe de degré maximum D au moins 4 et de degré moyen maximum inférieur à 7/3 admet une coloration à distance 2 utilisant (D+1) couleurs. Ce résultat est optimal, et améliore des résultats existants de Dolama et Sopena, et Borodin et al.
Type de document :
Communication dans un congrès
Eurocomb'11: European Conference on Combinatorics, Graph Theory and Applications, Aug 2011, Budapest, Hungary. Elsevier, 38, pp.155-160, 2011, Electronic Notes in Discrete Mathematics. 〈http://www.renyi.hu/conferences/ec11/〉. 〈10.1016/j.endm.2011.09.027〉
Liste complète des métadonnées

Littérature citée [5 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00782852
Contributeur : Marthe Bonamy <>
Soumis le : mercredi 30 janvier 2013 - 16:52:38
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : lundi 17 juin 2013 - 17:43:45

Fichier

blp11.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Marthe Bonamy, Benjamin Lévêque, Alexandre Pinlou. 2-distance coloring of sparse graphs. Eurocomb'11: European Conference on Combinatorics, Graph Theory and Applications, Aug 2011, Budapest, Hungary. Elsevier, 38, pp.155-160, 2011, Electronic Notes in Discrete Mathematics. 〈http://www.renyi.hu/conferences/ec11/〉. 〈10.1016/j.endm.2011.09.027〉. 〈lirmm-00782852〉

Partager

Métriques

Consultations de la notice

144

Téléchargements de fichiers

272