The El-Zahar-Erdős conjecture asserts that, for all positive integers
and
, every finite simple
graph of clique number less than
and sufficiently large chromatic
number contains two vertex-induced subgraphs
with disjoint vertex sets,
each of chromatic number at least
, 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 and
,
they constructed a finite simple
graph of chromatic number at least
and girth at least
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
and
.
The authors report substantive assistance from GPT-6.2 Astra in constructing the
counterexample and developing its proof.