betaFeedback

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 g≥4g \ge 4, we show by a probabilistic argument that there exist graphs of girth at least gg 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.

Paper details

vlnc:W_defjwckr
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

OpenAI’s GPT-6.2 Astra

View statement
Looking for related papers…