Sparse chromatic graphs and the complete-graph triangle bound

Abstract

We prove that there is an absolute constant $c>0$ such that every graph of chromatic number at least $r$ and at most $c{r}^3{\log }^{2}r$ edges contains at least $\left(\genfrac{}{}{0ex}{}{r}{3}\right)$ triangles. The proof has three ingredients. First, a sparse-core argument based on a triangle-sensitive coloring estimate of Harris extracts, from any counterexample, an induced subgraph of order $O(r)$ and chromatic number at least $(1-\eta )r$. Second, we prove an order-uniform stability theorem: for every $\beta >0$ there is $\gamma >0$, independent of the constant in the linear order bound, such that every sufficiently large $s$-critical graph $J$ of order $O(s)$ with $\omega (J)\le (1-\beta )s$ has at least $\left(\genfrac{}{}{0ex}{}{s}{3}\right)+\gamma s^3$ triangles. The proof combines the excess method and the modified-independent-set argument of Fox, Tidor, and Zhang. Third, we prove the exact bound when the graph contains a clique of order at least $(1-\delta )r$. This uses a new dense common-palette list analogue of Harris's edge--triangle estimate: if every list occupies a fixed positive proportion of a common palette, then the edge-triangle coloring bound survives up to a constant factor.