{"id":"arxiv/2611.24735","url":"https://arxiv.org/abs/2611.24735","tags":["math.CO"],"score":0,"title":"A disproof of the El-Zahar--Erdős conjecture","domain":"math.CO","source":"arxiv","authors":["Chenghua Liu","Boning Meng"],"reviews":0,"subject":"math.CO","summary":"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 $g \\ge 4$, we show by a probabilistic argument that there exist graphs of girth at least $g$ 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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-18","reactions":{}}