Graphs and Matroids Seminar

Title: Coloring Graphs of Bounded Maximum Degree with Small Clique Number

Abstract: Greedy coloring yields an upper bound on the chromatic number $\chi$ of $\Delta+1$ for graphs of maximum degree at most $\Delta$, which is tight for cliques.  Much attention has been devoted to improving this ``greedy bound" for graphs without large cliques. Brooks famously proved it can be improved by one for graphs with no clique of size $\Delta+1$ if $\Delta\ge 3$.  Reed conjectured it can be improved by $k$ for graphs with no clique of size larger than $\Delta +1-2k$. Johansson improved the greedy bound by a factor of $\Omega(\ln \Delta)$ or $\Omega(\ln \Delta/ \ln \ln \Delta)$ for graphs without triangles or cliques of any fixed size, respectively.