Determine f_r(n): fewest edges forcing a triangle in an n-vertex graph of chromatic number ≥ r (Erdős #1011)
Statement
For an integer $r\geq 2$, let $f_r(n)$ be the least number of edges such that every graph on $n$ vertices that has at least $f_r(n)$ edges and chromatic number at least $r$ must contain a triangle. Determine $f_r(n)$.
Acceptance. FULLY RESOLVES: determine $f_r(n)$ for all $r$ — an exact formula, equivalently pin down the leading constant of $g(r)$ (currently trapped between $(\tfrac12-o(1))r^2\log r$ and $(2+o(1))r^2\log r$) — with a complete proof. ADVANCES, any of: (a) determine the next exact case $f_5(n)$ for all large $n$ with proof, in the style of the $f_4$ result of Ren–Wang–Wang–Yang; (b) improve the bounds on $g(r)$ stated in the background (a lower constant above $1/2$ or an upper constant below $2$), strictly better than the best bound stated above, with proof; (c) compute exact $f_r(n)$ for new small pairs $(r,n)$ by extremal search, delivering the extremal graph and an exhaustiveness certificate that no graph with more edges, $n$ vertices and chromatic number $\geq r$ is triangle-free. Deliver the formula/proof, or the search code + certificate.
Background
Posed by Erdős [Er71]. Turán's theorem gives $f_2(n)=\lfloor n^2/4\rfloor+1$, and Erdős and Gallai [Er62d] proved $f_3(n)=\lfloor\tfrac{1}{4}(n-1)^2\rfloor+2$. Simonovits, in his PhD thesis (see p.358 of [Si74]), showed $$f_r(n)=\frac{n^2}{4}-\frac{g(r)}{2}n+O(1),$$ where $g(r)$ is the largest $m$ such that every triangle-free graph with chromatic number at least $r$ needs at least $m$ vertices deleted to become bipartite. Simonovits bounded $\tfrac{\log r}{\log\log r}r^2\ll g(r)\ll (\log r)^2 r^2$; more recently the order was pinned to $g(r)\asymp r^2\log r$, in fact $(\tfrac12-o(1))r^2\log r\leq g(r)\leq (2+o(1))r^2\log r$, the lower bound from Davies and Illingworth [DaIl22] (cf. erdosproblems.com/1104) and the upper bound from Hefty, Horn, King and Pfender [HHKP25] via bounds on the Ramsey number $R(3,k)$. Ren, Wang, Wang and Yang [RWWY24] determined the next exact case: for $n\geq 150$, $f_4(n)=\lfloor\tfrac{(n-3)^2}{4}\rfloor+6$. Thus $f_2,f_3,f_4$ are known exactly, while $f_5$ and the general $r$ (equivalently, the exact constant in $g(r)$) remain open. Listed as open on erdosproblems.com/1011 (fetched 2026-07-13, status 'open', tagged 'graph theory'); closely tied to the dual triangle-free chromatic problem #1013 and to the venue problem on making triangle-free graphs bipartite (Erdős #23). Attacker's tool: extremal / exhaustive search for the next exact case $f_5(n)$ and improved constructions of triangle-free high-chromatic graphs to sharpen the $g(r)$ constant, plus $R(3,k)$ bound transfer.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1011 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.