Problem 1111

If $G$ is a finite graph and $A,B$ are disjoint sets of vertices then we call $A,B$ anticomplete if there are no edges between $A$ and $B$ .

If $t,c\geq 1$ then there exists $d\geq 1$ such that if $\chi(G)\geq d$ and $\omega(G)<t$ then there are anticomplete sets $A,B$ with $\chi(A)\geq \chi(B)\geq c$ .

Source: erdosproblems.com/1111

Graph theory

Wiki page

Status

Open

No claim settles this problem.

Open. The most recent refereed treatment, Problem 1.1 of [NSS24] (J. Combin. Theory Ser. B 165 (2024), 211--222; cited in the arXiv v1 text of March 2023), restates the statement in the site's letters and says "This remains open." What is settled: $c=2$ for every $t$ , through Wagon's Theorem of [Wa80b] (J. Combin. Theory Ser. B 1980, refereed), $\chi(G)\le\binom{\omega(G)+1}2$ for graphs with no induced $K_2\cup K_2$ , so $d(t,2)\le\binom t2+1$ , with $d(2,2)=2$ , $d(3,2)=4$ , $d(4,2)=5$ as [ElEr85] reports them; and $c=3$ for every $t$ , by Corollary 3 (Elzahar 1985) of [ElEr85] (Combinatorica 1985, refereed), $d(t,3)\le2\binom{t-1}3+7\binom{t-1}2+t$ for $t>3$ , from Theorem 2 (Elzahar 1985), $d(3,3)\le8$ , and the reduction Theorem 1. Both cases are recorded as accepted partial claims, on Wagon 1980 and El-Zahar and Erdős 1985. For $c\ge4$ nothing found decides the statement for any $t\ge3$ (the cases $t\le2$ are trivial); Erdős wrote in 1985 that "great difficulties appeared for $k=4$ " ([Er85b], p. 206). The strongest partial results are 1.2 of [NSS24], the statement with $\chi(A)\ge c$ weakened to minimum degree at least $c$ on $A$ , and 1.3, a minimum-degree variant with $K_{t,t}$ excluded instead of $K_t$ ; neither settles an instance of the statement, so neither is a claim. No proof or disproof was found in the search whose scope the Current assessment records; this is a bounded negative finding, not a certificate of openness.

ElEr85: El-Zahar, M. and Erdős, P., On the existence of two non-neighboring subgraphs in a graph. Combinatorica 5 (1985), no. 4, 295--300, doi:10.1007/BF02579243 (Crossref record read; received 13 October 1984, revised 15 January 1985). The question and the reduction, p. 295; Wagon's bound, the small values, Theorems 1--2, p. 296; the Mycielski remark and Corollary 3, p. 297. Library home: Elzahar 1985 (the Rényi archive's scan 1985-18.pdf); paged at Elzahar 1985, Theorem 1 (p. 296), Elzahar 1985, Theorem 2 (p. 296) and Elzahar 1985, Corollary 3 (p. 297).
Er85b: Erdős, P., Problems and results on chromatic numbers in finite and infinite graphs. Graph theory with applications to algorithms and computer science (Kalamazoo, Mich., 1984), Wiley-Interscience (1985), 201--213 (the site's reference text). The passage, printed p. 206, is PDF p. 6 of the Rényi archive's scan 1985-26.pdf. Library home: Erdős 1985; paged at Erdős 1985, The El-Zahar-Erdős problem restated (p. 206).
Wa80b: Wagon, S., A bound on the chromatic number of graphs without certain induced subgraphs. J. Combin. Theory Ser. B 29 (1980), no. 3, 345--346, doi:10.1016/0095-8956(80)90093-3 (the Crossref record carries the publisher's open-archive license dated 2013-07-17); the publisher's open-archive file has 2 pages, printed pp. 345--346 = PDF pp. 1--2. The Theorem and its proof, p. 345, the proof ending on p. 346; the sharpness remarks, the $n\cdot K_2$ generalization and the references, p. 346. Library home: Wagon 1980; paged at Wagon 1980, Theorem (p. 345).
NSS24: Nguyen, T., Scott, A. and Seymour, P., On a problem of El-Zahar and Erdős. J. Combin. Theory Ser. B 165 (2024), 211--222, doi:10.1016/j.jctb.2023.11.004 (published March 2024; Crossref record read); arXiv:2303.13449v1 (23 March 2023, "February 6, 2023; revised March 24, 2023", a title page and an abstract page before 8 printed pages, not held; the only arXiv version). Problem 1.1 and results 1.2--1.3, printed p. 1 = PDF p. 3; Conjecture 4.1 and the references, p. 8 = PDF p. 10. Library home: Nguyen 2024; paged at Nguyen 2024, Problem 1.1 (p. 1), Nguyen 2024, 1.2 (p. 1) and Nguyen 2024, 1.3 (p. 1).
KlNe24: Klingelhoefer, F. and Newman, A., Bounding the chromatic number of dense digraphs by arc neighborhoods. arXiv:2307.04446; Combinatorica (2024), doi:10.1007/s00493-024-00098-z per a citation record read. Not held; named in the thread comment of 8 December 2025 for a tournament reformulation; a lead.
NSS23: Nguyen, T., Scott, A. and Seymour, P., Some results and problems on tournament structure. arXiv:2306.02364; J. Combin. Theory Ser. B (2025), doi:10.1016/j.jctb.2025.02.002 per a citation record read. Not held; the published form of the manuscript that [NSS24] cites as its [5] is a plausible identification made by title only, not checked.

Problem 1111

Status

Proof claims

Discussion