2-distance coloring of sparse graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2011

2-distance coloring of sparse graphs

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.
Fichier principal
Vignette du fichier
blp11.pdf (105.98 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-00782852 , version 1 (30-01-2013)

Identifiants

Citer

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. pp.155-160, ⟨10.1016/j.endm.2011.09.027⟩. ⟨lirmm-00782852⟩
214 Consultations
406 Téléchargements

Altmetric

Partager

More