Problem 620

If $G$ is a graph on $n$ vertices without a $K_4$ then how large a triangle-free induced subgraph must $G$ contain?

Graph theory

Wiki page

Status

ClaimedAnswered

A full solution has been claimed but not yet accepted. Settled in another form, for example when its parts resolve differently or the question is open-ended.

OPEN, the site's label, with the site's note that no finite computation can settle the question. The derived standing departs from the label: it is claimed, with the value answered, because a pending full claim answers the question. A preprint of 17 July 2026 by Morris, Sahasrabudhe and Verstraëte claims $f(n)=\Theta(\sqrt{n\log n})$ , which would determine the order asked for up to constants; it is unrefereed and not held in the library, and is recorded as claimed on its claim page (Morris Sahasrabudhe Verstraete, 2026). The bounds that refereed papers print for $f(n)$ leave a factor of order $(\log n\log\log n)^{1/2}$ :

c\,\sqrt{\frac{n\log n}{\log\log n}}\ \le\ f(n)\ \le\ 2^{300}\sqrt n\,\log n

for all large $n$ . The upper bound is Theorem 1 of Mubayi and Verstraete ( $f_s(n)=O(\sqrt n\log n)$ for each fixed $s\ge3$ , with the explicit constant $2^{100s}$ given after the theorem; Bull. Lond. Math. Soc. 57 (2025), 582--598, refereed; the library holds the arXiv v2), recorded as an accepted partial claim on its claim page (Mubayi and Verstraete, 2024). The lower bound rests on Shearer's (1995) Corollary 1 applied to a vertex neighborhood, the deduction that equation (1) of Mubayi and Verstraete's paper records in the form $c\sqrt{n\log n}/\log\log n$ , which the site prints; with the degree threshold balanced the same argument gives the larger $c\sqrt{n\log n/\log\log n}$ , first printed with this argument by Dudek and Mubayi [DM14], whom Mubayi and Verstraete and Gishboliner, Janzer and Sudakov credit. It is recorded as an accepted partial claim on its claim page (Dudek and Mubayi, 2013), and the deduction is written out on the corollary's result page. No refereed source determining the order was found in the search whose scope the Current assessment records; the July 2026 preprint found by it is the claim above, which the site has not adopted. This is a bounded negative finding about the refereed record, not a certificate of openness. Refereed results give more than they print: Corollary 2 of [JMRS21] yields $f(n)\ge c\sqrt{n\log n}$ in one line, as the Current assessment records, so the gap they leave is of order $(\log n)^{1/2}$ , subject to the unexamined claim of a gap in that paper's Theorem 1 recorded on Problem 610.

ErRo62: Erdős, P. and Rogers, C. A., The construction of certain graphs. Canad. J. Math. 14 (1962), 702--707, doi:10.4153/CJM-1962-060-4 (received October 26, 1961). The Section 3 Theorem and its Remark, p. 704. Library home: Erdős and Rogers 1962 (its edition a Rényi archive scan).
EGT92: Erdős, P., Gallai, T. and Tuza, Zs., Covering the cliques of a graph with vertices. Discrete Math. 108 (1992), 279--289, doi:10.1016/0012-365X(92)90681-5. Problem 3, printed p. 281. Library home: Erdős, Gallai and Tuza 1992.
Kr94: Krivelevich, M., $K^s$ -free graphs without large $K^r$ -free subgraphs. Combin. Probab. Comput. 3 (1994), no. 3, 349--354, doi:10.1017/S0963548300001243. The copy read is the author's typescript, paginated 1--5 (no file held); locators below are its pages. The definition and the Bollobás--Hind bounds, p. 1; $f_{3,4}(7)=4$ and Theorem 1, p. 2; Theorem 2 and Corollaries 1--2, p. 5. Library home: Krivelevich 1994.
MuVe24: Mubayi, D. and Verstraete, J., On the order of Erdős-Rogers functions. arXiv:2401.02548v2 (8 February 2024; title page dated February 12, 2024), retained; published as "On the order of the classical Erdős–Rogers functions", Bull. Lond. Math. Soc. 57 (2025), no. 2, 582--598, doi:10.1112/blms.13214 (published online 20 December 2024; the journal text is not held). Equation (1), Theorem 1 and the constant $2^{100s}$ , p. 1; Section 4, p. 4. Library home: Mubayi 2024.
Sh95: Shearer, J. B., On the independence number of sparse graphs. Random Structures Algorithms 7 (1995), no. 3, 269--271, doi:10.1002/rsa.3240070305 (received 12 July 1994, accepted 13 March 1995). Corollary 1, printed p. 271: $\alpha\ge c(r)\,n\ln d/(d\ln\ln d)$ for $K_r$ -free graphs ( $r\ge4$ ) on $n$ vertices with maximum degree $d$ and large $d$ , the bound [MuVe24]'s equation (1) applies to a vertex neighborhood. Library home: Shearer 1995 (no file is held); result page Corollary 1, which records the neighborhood argument.
BoHi91: Bollobás, B. and Hind, H. R., Graphs without large triangle free subgraphs. Discrete Math. 87 (1991), no. 2, 119--131, doi:10.1016/0012-365X(91)90042-Z (received 21 April 1987, revised 25 January 1989). The definitions of $h_r(G)$ and $f_{r,s}(n)$ , printed pp. 119--120; Theorem 1 with its proof, p. 120; Theorem 2, p. 121; Theorem 5, p. 127; Theorem 6, p. 128; Theorem 9, Corollary 10 and the closing paragraph, p. 131; the proofs of Theorems 2, 5 and 9 are checked for structure only. Library home: Bollobás and Hind 1991 (from the publisher's open-archive copy; no file is held); result pages Theorem 1 (Bollobás and Hind 1991) and Theorem 5.
Wo13: Wolfovitz, G., $K_4$ -free graphs without large induced triangle-free subgraphs. Combinatorica 33 (2013), no. 5, 623--631, doi:10.1007/s00493-013-2845-x (received June 13, 2011). The definitions and Theorem 1.1, printed p. 623; Theorem 1.2, its derivation of Theorem 1.1, the consequence $\ln f_{3,4}(n)=0.5\ln n+O(\ln\ln n)$ and the account of the author's preprint, p. 624; the proof, pp. 624--630, is checked for structure only. Library home: Wolfovitz 2013 (from the publisher's production text; no file is held); result page Theorem 1.1 (Wolfovitz 2013). The author's earlier preprint "The $K_4$ -free process", arXiv:1008.4044v1 (24 August 2010, 36 pp.; abstract only), is the paper's reference [16] and proves only the weaker by-product $f(n)=O(n^{3/5}(\ln n)^{1/5})$ , which the paper describes (p. 624) as a $(\ln n)^{3/10}$ factor improvement of Krivelevich's upper bound, not the Combinatorica bound.
DRR14: Dudek, A., Retter, T. and Rödl, V., On generalized Ramsey numbers of Erdős and Rogers. J. Combin. Theory Ser. B (2014); arXiv:1309.4521 (18 September 2013). Not held; the bounds $f_3(n)=O(\sqrt n(\log n)^{32})$ and $f_s(n)=O(\sqrt n(\log n)^{2(s+1)^2})$ are quoted from [MuVe24], p. 1.
DM14: Dudek, A. and Mubayi, D., On generalized Ramsey numbers for 3-uniform hypergraphs. J. Graph Theory 76 (2014), no. 3, 217--223, doi:10.1002/jgt.21760 (published online 21 August 2013); arXiv:1309.4518 (v1, 18 September 2013). Introduction, p. 2 of the arXiv text: Shearer's bound with the neighborhood argument gives $f_{s,s+1}(n)=\Omega((n\log n/\log\log n)^{1/2})$ for $s\ge3$ . Credited by [MuVe24] (p. 1, "As observed by Dudek and the first author") and by [GJS25] (p. 2, their reference [10]). Recorded on its claim page (Dudek and Mubayi, 2013).
GJS25: Gishboliner, L., Janzer, O. and Sudakov, B., Induced subgraphs of $K_r$ -free graphs and the Erdős–Rogers problem. Combinatorica 45 (2025), no. 2, article 23, 20 pp., doi:10.1007/s00493-025-00147-1 (received 16 September 2024, accepted 15 February 2025, published online 27 March 2025); arXiv:2409.06650. A copy of the published article (pp. 1--3 used) is filed as Gishboliner and Sudakov 2025. The pages used are its introduction (p. 2) and its Theorem 1.2 with the remark after it (p. 3).
MSV26: Morris, R., Sahasrabudhe, J. and Verstraëte, J., On the Erdős-Rogers function. arXiv:2607.16118v1 (17 July 2026), 22 pp.; no journal reference on the arXiv record (2026-10-07); not held, its abstract the source of this page's account. Claim, recorded below.
JMRS21: Joret, G., Micek, P., Reed, B. and Smid, M., Tight bounds on the clique chromatic number. Electron. J. Combin. 28 (2021), no. 3, Paper P3.51, doi:10.37236/9659. Not held; library card Joret 2021, result page Corollary 2. The ingredient the [MSV26] abstract names for its lower bound.
Er99: Erdős, Paul, A selection of problems and results in combinatorics. Combin. Probab. Comput. 8 (1999), 1--6. Site source key; not held.

Problem 620

Status

Proof claims

Discussion