Skip to Main content Skip to Navigation
Journal articles

Brooks’ theorem on powers of graphs

Marthe Bonamy 1 Nicolas Bousquet 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Complete list of metadatas

Cited literature [10 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01264422
Contributor : Alexandre Pinlou <>
Submitted on : Friday, December 20, 2019 - 12:53:25 PM
Last modification on : Friday, December 20, 2019 - 2:40:18 PM
Document(s) archivé(s) le : Saturday, March 21, 2020 - 6:50:17 PM

File

1310.5493.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Marthe Bonamy, Nicolas Bousquet. Brooks’ theorem on powers of graphs. Discrete Mathematics, Elsevier, 2014, 325, pp.12-16. ⟨10.1016/j.disc.2014.01.024⟩. ⟨lirmm-01264422⟩

Share

Metrics

Record views

235

Files downloads

94