Brooks’ theorem on powers of graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Discrete Mathematics Year : 2014

Brooks’ theorem on powers of graphs

Marthe Bonamy
Nicolas Bousquet

Abstract

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

Dates and versions

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

Identifiers

Cite

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⟩
109 View
102 Download

Altmetric

Share

More