Problem 917

Erdős Problem #917: declared status 'open'. Formalized: no. Let $k\geq 4$ and $f_k(n)$ be the largest number of edges in a graph on $n$ vertices which has chromatic number $k$ and is critical (i.e. deleting any edge reduces the chromatic number). Is it true that$$f_k(n) \gg_k n^2?$$Is it true that$$f_6(n)\sim n^2/4?$$More generally, is it true that, for $k\geq 6$,$$f_k(n) \sim \frac{1}{2}\left(1-\frac{1}{\lfloor k/3\rfloor}\right)n^2?$$ Current best: Erd\H{o}s [Er69b] observed that Dirac's construction generalises to show that, if $3\mid k$, there are infinitely many values of $n$ (those of the shape $mk/3$ where $m$ is odd) such that$$f_k(n) \geq \frac{1}{2}\left(1-\frac{1}{k/3}\right)n^2 + n.$$Toft [To70] proved that $f_k(n)\gg_k n^2$ for $k\geq 4$. Constructions of Stiebitz [St87] show that, for $k\geq 6$, there exist infinitely many values of $n$ such that$$f_k(n) \geq \frac{1}{2}\left(1-\frac{1}{\lfloor k/3\rfloor+\delta_k}\right)n^2$$where $\delta_k=0$ if $k\equiv 0\pmod{3}$, $\delta_k=1/7$ if $k\equiv 1\pmod{3}$, and $\delta_k\equiv 24/69$ if $k\equiv 2\pmod{3}$, which disproves Erd\H{o}s' conjectured asympotic for $k\not\equiv 0\pmod{3}$. Stiebitz also proved the general upper bound$$f_k(n) < \mathrm{ex}(n;K_{k-1})\sim \frac{1}{2}\left(1-\frac{1}{k-2}\right)n^2$$for large $n$. Luo, Ma, and Yang [LMY23] have improved this upper bound to$$f_k(n) \leq \frac{1}{2}\left(1-\frac{1}{k-2}-\frac{1}{36(k-1)^2}+o(1)\right)n^2$$See also [944] and [1032]. Prize: no. Tags: chromatic number, graph theory.