El-Zahar–Erdős conjecture

Status partial high confidence

The El-Zahar–Erdős conjecture (1985/1986) asks whether every graph with chromatic number at least f(r,k) must contain either an r-clique or an induced subgraph that is the disjoint union of two k-chromatic graphs (equivalently, two anticomplete subgraphs each with chromatic number at least k). The full conjecture remains open. Nguyen, Scott, and Seymour (2023) proved a weaker variant: for all t, c ≥ 1 there exists d such that if χ(G) ≥ d and ω(G) < t, then G has anticomplete subgraphs A, B where one has minimum degree at least c and the other has chromatic number at least c—but not both chromatic number at least c as the conjecture requires. The problem was still listed as open at the Barbados 2025 Graph Theory Workshop.

Cited literature (1)

• partial On a problem of El-Zahar and Erdős (2023)
  Tung Nguyen, Alex Scott, Paul Seymour · Journal of Combinatorial Theory, Series B · arXiv:2303.13449

  Proves that if χ(G) ≥ d and ω(G) < t, then G contains anticomplete subgraphs A, B where A has minimum degree at least c and B has chromatic number at least c; this is strictly weaker than the conjecture which requires both A and B to have chromatic number at least c.

Reviewer notes. The Bondy–Murty formulation (induced subgraph = disjoint union of two k-chromatic graphs) is equivalent to the standard anticomplete formulation: two vertex-disjoint, edge-free-between-them subgraphs each of chromatic number at least k. The 2023 Nguyen–Scott–Seymour paper (arXiv:2303.13449) appeared in JCTB (ScienceDirect pii S0095895623000989, verified as a returned search result but 403 on direct fetch). The partial result weakens the conclusion for one of the two subgraphs (minimum degree instead of chromatic number). The problem remains open in particular for triangle-free graphs (ω(G) ≤ 2).

Auto-reviewed 2026-09-10 with claude-sonnet-4-6 (web search enabled).