Brooks’ theorem on powers of graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue Discrete Mathematics Année : 2014

Brooks’ theorem on powers of graphs

Marthe Bonamy
Nicolas Bousquet

Résumé

We prove that for k ≥ 3, the bound given by Brooks' theorem on the chromatic number of k-th powers of graphs of maximum degree ∆ ≥ 3 can be lowered by 1, even in the case of online list coloring.
Fichier principal
Vignette du fichier
1310.5493.pdf (110.23 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-01264422 , version 1 (20-12-2019)

Identifiants

Citer

Marthe Bonamy, Nicolas Bousquet. Brooks’ theorem on powers of graphs. Discrete Mathematics, 2014, 325, pp.12-16. ⟨10.1016/j.disc.2014.01.024⟩. ⟨lirmm-01264422⟩
110 Consultations
102 Téléchargements

Altmetric

Partager

More