Critical graphs without triangles: an optimum density construction

Abstract

We construct dense, triangle-free, chromatic-critical graphs of chromatic number $k$ for all $k\ge 4$. For $k\ge 6$ our constructions have $>(\frac{1}{4}-\epsilon )n^2$ edges, which is asymptotically best possible by Turán's theorem. We also demonstrate (nonconstructively) the existence of dense $k$-critical graphs avoiding all odd cycles of length $\le \ell$ for any $\ell$ and any $k\ge 4$, again with a best possible density of $>(\frac{1}{4}-\epsilon )n^2$ edges for $k\ge 6$. The families of graphs without triangles or of given odd-girth are thus rare examples where we know the correct maximal density of $k$-critical members ($k\ge 6$).

17 pages, 5 figures, 1 table (published version)