- 运筹控制分论坛
Coloring claw-free graphs with $\Delta-1$ colors
Prof. Dan Cranston(Virginia Commonwealth University)
2018-01-01 12:13 华东师范大学
In 1977, Borodin and Kostochka conjectured that every graph with maximum degree $\Delta\ge 9$ with no clique on $\Delta$ vertices has chromatic number at most $\Delta-1$. We prove this conjecture for claw-free graphs, i.e., those with no induced $K_{1,3}$. This is joint work with Landon Rabern, of Arizona State University.
