Triangle-free four-chromatic graphs (Q1901038)

Given natural numbers \(r\) and \(t\), let \(n(r, t)\) be the minimum order of a \(K^r\)-free graph \(G\) with chromatic number \(\chi(G)\geq t\). Let \[ \psi(n, K^r, t)= \max\{\delta(G)\mid K^r\subset G,\;\chi(G)\geq t,\;|G|= n\geq n(r, t)\}. \] \textit{R. Häggkvist} [Ann. Discrete Math. 13, 89-99 (1982; Zbl 0492.05047)] proved that \[ \psi(n, K^3, 4)\geq {10\over 29} n\quad\text{if} \quad 29|n. \] A nice example led Häggkvist to conjecture that \[ \psi(n, K^3, 4)= {10\over 29} n\quad\text{if} \quad 29|n. \] The main result of this paper is Theorem 9: For \(n\geq 11\), \[ \psi(n, K^3, 4)= \begin{cases} {10(n- 3)\over 29}\quad & \text{if } 29|(n- 3)\text{ and } n\geq 33\\ \lfloor{10n\over 29}\rfloor\quad & \text{otherwise}.\end{cases} \] Häggkvist's conjecture follows from Theorem 9. The author also published the paper [Comb. Probab. Comput. 2, No. 4, 479-490 (1993; Zbl 0792.05078)] studying the structure of \(K^3\)-free graphs \(G\) of order \(n\) with \(\delta(G)> {10n\over 29}\).