Title:Â Coloring Graphs of Bounded Maximum Degree with Small Clique Number
| Speaker: | Tom Kelly |
| Affiliation: | University of À¶Ý®ÊÓƵ |
| Room: | MC 5479 |
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.