David Mikšaník: Coloring graphs with Δ-1 colors
Every graph G with maximum degree Δ(G) can be (properly) colored with Δ(G)+1 colors by coloring the vertices greedily. Much research has focused on improving this greedy bound. The first general improvement goes back to Brooks (1941), who characterized graphs that can be colored with Δ(G) colors.
In this talk, we consider the next case. We survey what is known about graphs that can be colored with Δ(G)-1 colors, discuss related results and conjectures, and present some of our contributions. In particular, we present our recent result showing that every triangle-free graph G with maximum degree Δ(G)≥12 is (Δ(G)-1)-choosable.
This talk is based on joint work with Zdeněk Dvořák and Ross Kang.