TOPICS
Search

El-Zahar-Erdős Conjecture


The El-Zahar-Erdős conjecture asserts that, for all positive integers t and c, every finite simple graph of clique number less than t and sufficiently large chromatic number contains two vertex-induced subgraphs with disjoint vertex sets, each of chromatic number at least c, with no graph edge between them (El-Zahar and Erdős 1985).

Liu and Meng (2026) refuted the conjecture even for triangle-free graphs. For every pair of integers d>=1 and g>=4, they constructed a finite simple graph of chromatic number at least d and girth at least g such that, whenever two vertex-induced subgraphs with disjoint vertex sets have no graph edge between them, at least one has chromatic number at most 6. Thus the conjecture fails already for t=3 and c=7. The authors report substantive assistance from GPT-6.2 Astra in constructing the counterexample and developing its proof.


See also

Chromatic Number, Clique Number, Triangle-Free Graph, Vertex-Induced Subgraph

Explore with Wolfram|Alpha

References

El-Zahar, M. and Erdős, P. "On the Existence of Two Non-Neighboring Subgraphs in a Graph." Combinatorica 5, 295-300, 1985. https://doi.org/10.1007/BF02579243.Liu, C. and Meng, B. "A Disproof of the El-Zahar-ErdŐs Conjecture." 18 Nov 2026. https://arxiv.org/abs/2611.24735v1.

Cite this as:

Weisstein, Eric W. "El-Zahar-Erdős Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/El-Zahar-ErdosConjecture.html

Subject classifications