2013/10/21 by Bonamy, Marthe, Bousquet, Nicolas
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1310.5493
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.