Reza Naserasr, Simon Fraser University
talks on:
"On $\Delta$-critical graphs"

Abstract:
A graph is $\Delta$-critical if it has chromatic number equal to its maximum degree, and every proper subgraph has a strictly smaller chromatic number. In 1977, Borodin and Kostochka conjectured that for $\Delta \geq 9$ there is no $\Delta$-critical graph. If true, this would be an extension of Brooks theorem. In 1997 B. Reed proved this conjecture for large $\Delta$, using the probablilistic method. Here we show that any counterexample to this conjecture must have at least $3 \Delta - 6$ vertices.