On a problem of El-Zahar and Erdős

Tung Nguyen, Alex Scott, Paul Seymour

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

Two subgraphs A,B of a graph G are anticomplete if they are vertex-disjoint and there are no edges joining them. Is it true that if G is a graph with bounded clique number, and sufficiently large chromatic number, then it has two anticomplete subgraphs, both with large chromatic number? This is a question raised by El-Zahar and Erdős in 1986, and remains open. If so, then at least there should be two anticomplete subgraphs both with large minimum degree, and that is one of our results. We prove two variants of this. First, a strengthening: we can ask for one of the two subgraphs to have large chromatic number: that is, for all t,c≥1 there exists d≥1 such that if G has chromatic number at least d, and does not contain the complete graph Kt as a subgraph, then there are anticomplete subgraphs A,B, where A has minimum degree at least c and B has chromatic number at least c. Second, we look at what happens if we replace the hypothesis that G has sufficiently large chromatic number with the hypothesis that G has sufficiently large minimum degree. This, together with excluding Kt, is not enough to guarantee two anticomplete subgraphs both with large minimum degree; but it works if instead of excluding Kt we exclude the complete bipartite graph Kt,t. More exactly: for all t,c≥1 there exists d≥1 such that if G has minimum degree at least d, and does not contain the complete bipartite graph Kt,t as a subgraph, then there are two anticomplete subgraphs both with minimum degree at least c.

Original languageEnglish (US)
Pages (from-to)211-222
Number of pages12
JournalJournal of Combinatorial Theory. Series B
Volume165
DOIs
StatePublished - Mar 2024

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Chromatic number
  • Subgraphs

Fingerprint

Dive into the research topics of 'On a problem of El-Zahar and Erdős'. Together they form a unique fingerprint.

Cite this