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) ≫_{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} (1 - \frac{1}{⌊ k /3 ⌋}) n^{2} ?$

Worked, still open.

graph theory · open · 0 attempts

use this record

vela registry pull vfr_37aec80d874a0239

vela reproduce examples/erdos-problems

evidence

unverified AI candidates (2)

gpt-erdos · GPT-5.2 Pro + Deep Research · unverified

This is an old question of Dirac/Erdős (it is Erdős problem #917) and is still open in general. The short answers are:

llm-hunter · gpt pro 5.2 · unverified

1 LLM attack(s) recorded (gpt pro 5.2); unverified.

open