WorksMathematics
A disproof of the El-Zahar–Erdős conjecture
Abstract
El-Zahar and Erdős asked whether every graph of bounded clique number and sufficiently large chromatic number contains two vertex-disjoint induced subgraphs, each of large chromatic number, with no edge between them. We give a negative answer even for triangle-free graphs. For every integer , we show by a probabilistic argument that there exist graphs of girth at least and arbitrarily large chromatic number in which any two vertex-disjoint induced subgraphs that each require at least seven colors are joined by an edge.