= Triangle-free chromatic lower bound at bounded maximum degree
{title2=$\chi=\Omega(\Delta/\log\Delta)$}
Choose $n=d^7$ and a <binomial random graph> of edge probability $d/n$. With high probability its maximum degree is at most $2d$, it has $o(n)$ triangles, and every <independent set> has size at most $4n\log d/d$. Delete one vertex per triangle. The resulting <triangle-free graph> has chromatic number at least $d/(8\log d)$. Appending a disjoint star of degree $2d$, if necessary, makes the maximum degree exactly $2d$ without lowering the chromatic number. Thus the order $\Delta/\log\Delta$ is unavoidable.
Back to article page
