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
94 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More