Critical graphs without triangles: an optimum density construction

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} -\varepsilon)n^2$ edges, which is asymptotically best possible by Tur'an’s theorem. We also demonstrate (nonconstructively) the existence of dense $k$-critical graphs avoiding all odd cycles of length $\le \mathrm{\ell }$ for any $\mathrm{\ell }$ and any $k\ge 4$, again with a best possible density of $>(\frac{1}{4} -\varepsilon)n^2$edgesfor$k\geq 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$).