2-distance coloring of sparse graphs

Marthe Bonamy; Benjamin Lévêque; Alexandre Pinlou

doi:10.1016/j.endm.2011.09.027

Retour

Acte de colloque

Open Access

2-distance coloring of sparse graphs

Marthe Bonamy, Benjamin Lévêque et Alexandre Pinlou

Electronic Notes in Discrete Mathematics, Vol.38, pp.155-160

Electronic Notes in Discrete Mathematics

Eurocomb'11: European Conference on Combinatorics, Graph Theory and Applications (Budapest, Hungary, 29/08/2011–02/09/2011)

01/12/2011

DOI: https://doi.org/10.1016/j.endm.2011.09.027

Résumé

2-distance coloring

square coloring

maximum average degree

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.

Fichiers et liens (1)

url

Find in HALAfficher

Indicateurs

1 Consultations de la notice

Détails

Titre: 2-distance coloring of sparse graphs
Créateurs - sans rôle: Marthe Bonamy - Université de Montpellier
Benjamin Lévêque - Université de Montpellier
Alexandre Pinlou - Université de Montpellier
Détails de publication: Electronic Notes in Discrete Mathematics, Vol.38, pp.155-160
Colloque: Eurocomb'11: European Conference on Combinatorics, Graph Theory and Applications (Budapest, Hungary, 29/08/2011–02/09/2011)
Publications en série: Electronic Notes in Discrete Mathematics
Identifiants: 9944968209311
Unité académique: Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier - LIRMM
Langue: English
Type de ressource: Conference proceeding
Champs locaux: lirmm-00782852