Pure Pairs. II. Excluding All Subdivisions of A Graph

Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

We prove for every graph H there exists ɛ > 0 such that, for every graph G with |G|≥2, if no induced subgraph of G is a subdivision of H, then either some vertex of G has at least ɛ|G| neighbours, or there are two disjoint sets A, B ⊆ V(G) with |A|,|B|≥ɛ|G| such that no edge joins A and B. It follows that for every graph H, there exists c>0 such that for every graph G, if no induced subgraph of G or its complement is a subdivision of H, then G has a clique or stable set of cardinality at least |G|c. This is related to the Erdős-Hajnal conjecture.

Original languageEnglish (US)
Pages (from-to)379-405
Number of pages27
JournalCombinatorica
Volume41
Issue number3
DOIs
StatePublished - Jun 2021

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Pure Pairs. II. Excluding All Subdivisions of A Graph'. Together they form a unique fingerprint.

Cite this