2-distance coloring of sparse graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
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⟩
181 Consultations
359 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More