Problem 1011

Let $f_r(n)$ be minimal such that every graph on $n$ vertices with $\geq f_r(n)$ edges and chromatic number $\geq r$ contains a triangle. Determine $f_r(n)$ .

Source: erdosproblems.com/1011

Graph theory

Wiki page

Status

Open

No claim settles this problem.

Open. The exact values known are $f_2(n)=\lfloor n^2/4\rfloor+1$ (Turán's theorem, as the site says and as [Er62d] p. 122 records), $f_3(n)=\lfloor(n-1)^2/4\rfloor+2$ for $n\ge5$ (the upper bound is Lemma 1 of [Er62d], the Erdős--Gallai and Andrásfai theorem, and the matching triangle-free non-bipartite graph with one edge fewer is on p. 124 of the same paper and is the graph $H_0$ of [RWWY24]), and $f_4(n)=\lfloor(n-3)^2/4\rfloor+6$ for $n\ge90$ (Theorem 1.4 of [RWWY24], arXiv v2 of 19 October 2025, a preprint; the blow-ups of the Grötzsch graph give the matching lower bound). The site prints the range $n\ge150$ for the last value; v2 prints $n\ge90$ , a site-versus-source discrepancy recorded below. For general $r$ , Theorem 2.7 of [Si74] (p. 358; Simonovits attributes it to his thesis and prints no proof) gives $f_r(n)=\tfrac{n^2}4-\tfrac{g(r)}2n+O(1)$ with $g(r)=\hat g_3(r)$ , and Remark 2.8(a) of the same paper (p. 359) asserts without proof that $\tfrac{\log r}{\log\log r}r^2\ll g(r)\ll(\log r)^2r^2$ ; the site reports both, and, from its discussion thread, that $g(r)\asymp r^2\log r$ ; the inputs to the thread's derivation, Theorem 1 of [DaIl22] and Theorem 1.3 of [HHKP25], are checked on this page, but the derivation itself is a forum argument recorded with provenance and unverified. The three literature determinations have claim pages: Turán for $f_2(n)$ (accepted, a refereed partial claim), Erdős and Gallai for $f_3(n)$ (accepted, a refereed partial claim) and Ren, Wang, Wang and Yang for $f_4(n)$ with $n\ge90$ (a pending partial claim; the paper is a preprint). No source found determines $f_r(n)$ for any $r\ge5$ , or $f_4(n)$ for $n<90$ , beyond forum claims of September 2026 for $r=4$ and for $r=5$ with $n\ge80$ , recorded on two further pending partial claim pages below. No proof or disproof of a general formula was found in the search whose scope the Current assessment records; this is a bounded negative finding, not a certificate of openness.

Er71: Erdős, P., Some unsolved problems in graph theory and combinatorial analysis. Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), Academic Press (1971), 97--109; item 3, printed p. 98 (PDF p. 2 of the Rényi archive's scan). Library home: Erdős 1971; the passage is paged at Erdős 1971, Item 3 (p. 98).
Er62d: Erdős, P., On a theorem of Rademacher-Turán. Illinois J. Math. 6 (1962), no. 1, 122--127, doi:10.1215/ijm/1255631811 (Crossref record). Lemma 1, p. 123; the extremal example, p. 124. Library home: Erdős 1962 (the Rényi archive's scan 1962-09.pdf); paged at Erdős 1962, Lemma 1 (p. 123).
RWWY24: Ren, S., Wang, J., Wang, S. and Yang, W., Extremal triangle-free graphs with chromatic number at least four. arXiv:2404.07486 (v1 11 April 2024; v2 19 October 2025, "the proof is slightly improved", 14 pages). A preprint. Theorems 1.2 and 1.4, pp. 1--2. Library home: Ren et al. 2024; paged at Ren et al. 2024, Theorem 1.4 (p. 2) and Ren et al. 2024, Theorem 1.2 (p. 1).
Si74: Simonovits, M., Extremal graph problems with symmetrical extremal graphs. Additional chromatic conditions. Discrete Math. 7 (1974), no. 3--4, 349--376, doi:10.1016/0012-365X(74)90044-2 (received 12 September 1973, original version 30 March 1972; Crossref record, carrying the publisher's open-archive license dated 2013-07-17). Theorem 2.7, p. 358; Remark 2.8, p. 359; the site cites "the discussion on p. 358". Library home: Simonovits 1974 (the publisher's open-archive copy; the card carries the row for this problem); paged at Simonovits 1974, Theorem 2.7 (p. 358) and Simonovits 1974, Remark 2.8 (p. 359). The site's reference text misspells the title's first word ("Extermal").
DaIl22: Davies, E. and Illingworth, F., The $\chi$ -Ramsey problem for triangle-free graphs. SIAM J. Discrete Math. 36 (2022), no. 2, 1124--1134, doi:10.1137/21M1437573 (published online 28 April 2022; Crossref record); arXiv:2107.12288v2 (28 January 2022, 13 pages). Theorem 1, p. 3 of the preprint. Library home: Davies and Illingworth 2022; paged at Davies and Illingworth 2022, Theorem 1 (p. 3).
HHKP25: Hefty, Z., Horn, P., King, D. and Pfender, F., Improving $R(3,k)$ in just two bites. arXiv:2510.19718 (v3 19 February 2026, 18 pages); a preprint. Theorem 1.3, p. 2. Library home: Hefty et al. 2025; paged at Hefty et al. 2025, Theorem 1.3 (p. 2).

Problem 1011

Status

Proof claims

Discussion