2-distance coloring of sparse graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2011

2-distance coloring of sparse graphs

Abstract

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
Origin Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

Cite

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⟩
196 View
372 Download

Altmetric

Share

More