Brooks’ theorem on powers of graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
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⟩
102 View
92 Download

Altmetric

Share

Gmail Facebook X LinkedIn More