Excluding a substar and an antisubstar

Maria Chudnovsky, Sergey Norin, Bruce Reed, Paul Seymour

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

Ramsey's theorem says that for every clique H1 and for every graph H2 with no edges, all graphs containing neither of H1, H2 as induced subgraphs have bounded order. What if, instead, we exclude a graph H1 with a vertex whose deletion gives a clique, and the complement H2 of another such graph? This no longer implies bounded order, but it implies tightly restricted structure that we describe. There are also several related subproblems (what if we exclude a star and the complement of a star? what if we exclude a star and a clique? and so on) and we answer a selection of these.

Original languageEnglish (US)
Pages (from-to)297-308
Number of pages12
JournalSIAM Journal on Discrete Mathematics
Volume29
Issue number1
DOIs
StatePublished - 2015

All Science Journal Classification (ASJC) codes

  • General Mathematics

Keywords

  • Induced subgraphs
  • Ramsey's theorem

Fingerprint

Dive into the research topics of 'Excluding a substar and an antisubstar'. Together they form a unique fingerprint.

Cite this