Problem 917

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?

Source: erdosproblems.com/917

Graph theory
Chromatic number

Wiki page

Status

Open

No claim settles this problem.

Open. The site's label is OPEN. The three questions stand differently, and the frontmatter's standing is derived from the claim pages. Toft's constructions answer the first question yes and refute the third question's universal formula for $k\not\equiv0\pmod3$ , an accepted partial claim (claim page (Toft, 1970)); the site credits the constructions for $k\ge6$ to Stiebitz, while Luo, Ma and Yang credit them to Toft, a conflict that page records. Qiyuan Gu's preprint of September 2026, whose proofs the proof-claim entry says GPT 6 Astra generated, claims a refutation at $k=12$ , a multiple of $3$ , and is a pending partial claim (claim page (Gu, 2026)). The second question, $f_6(n)\sim n^2/4$ , and the formula's restriction to the other multiples of $3$ are open, so the problem has no full claim.

Di52: Dirac, G. A., A property of $4$ -chromatic graphs and some remarks on critical graphs. J. London Math. Soc. (1952), 85–92.
Er69b: Erdős, P., Problems and results in chromatic graph theory. Proof Techniques in Graph Theory (1969), 27–35.
Er93: Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. 16 (1993), 333--350; Chapter IV, printed p. 341: Dirac's 6-critical graph on $n$ vertices with more than $n^2/4$ edges, Toft's 4-chromatic critical graph with more than $n^2/16$ edges, and that $f_k(n)$ is unknown for $k>3$ , with not even the existence of $\lim f_k(n)/n^2=\lambda_k$ established. The site cites p. 341. Library home: Erdős 1993.
LMY23: Luo, Cong; Ma, Jie; and Yang, Tianchi, On the maximum number of edges in $k$ -critical graphs. Combin. Probab. Comput. 32 (2023), 900–911.
St87: Stiebitz, M., Subgraphs of colour-critical graphs. Combinatorica 7 (1987), 303–312.
To70: Toft, B., On the maximal number of edges of critical $k$ -chromatic graphs. Studia Sci. Math. Hungar. 5 (1970), 461–470.
Gu26: Gu, Qiyuan, Twelve-critical graphs with $(2/5+o(1))n^2$ edges. Zenodo record 22569201, version 7 (2026); unreviewed preprint lead.

Problem 917

Status

Proof claims

Discussion