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.
- Titre
- Brooks’ theorem on powers of graphs
- Créateurs - sans rôle
- Marthe Bonamy - Université de MontpellierNicolas Bousquet - Université de Montpellier
- Détails de publication
- Discrete Mathematics, Vol.325, pp.12-16
- Identifiants
- 99151459909311
- Unité académique
- Laboratoire d'Informatique de Robotique et de Microélectronique de Mtp - LIRMM
- Langue
- English
- Type de ressource
- Journal article
- Champs locaux
- lirmm-01264422