Skip to Main content Skip to Navigation
Conference papers

2-distance coloring of sparse graphs

Marthe Bonamy 1 Benjamin Lévêque 1, * Alexandre Pinlou 1
* Corresponding author
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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [5 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00782852
Contributor : Marthe Bonamy <>
Submitted on : Wednesday, January 30, 2013 - 4:52:38 PM
Last modification on : Tuesday, December 10, 2019 - 4:08:05 PM
Document(s) archivé(s) le : Monday, June 17, 2013 - 5:43:45 PM

File

blp11.pdf
Files produced by the author(s)

Identifiers

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. pp.155-160, ⟨10.1016/j.endm.2011.09.027⟩. ⟨lirmm-00782852⟩

Share

Metrics

Record views

291

Files downloads

603