Delphi.science

A disproof of the El-Zahar--Erdős conjecture

Source: arxiv.org/abs/2611.24735

Chenghua Liu, Boning Meng

arXivarxiv/2611.24735Nov 18, 2026math.COscore 0

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.

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.24735
curl -X POST /api/v1/records/arxiv/2611.24735/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.24735/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'