Erdős-Hajnal for cap-free graphs

Research output: Contribution to journalArticlepeer-review

Abstract

A “cap” in a graph G is an induced subgraph of G that consists of a cycle of length at least four, together with one further vertex that has exactly two neighbours in the cycle, adjacent to each other, and the “house” is the smallest, on five vertices. It is not known whether there exists ε>0 such that every graph G containing no house has a clique or stable set of cardinality at least |G|ε; this is the smallest open case of the Erdős-Hajnal conjecture and has been the subject of much study. We prove that there exists ε>0 such that every graph G with no cap has a clique or stable set of cardinality at least |G|ε.

Original languageEnglish (US)
Pages (from-to)417-434
Number of pages18
JournalJournal of Combinatorial Theory. Series B
Volume151
DOIs
StatePublished - Nov 2021

All Science Journal Classification (ASJC) codes

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

Keywords

  • Cap
  • Erdos-Hajnal conjecture
  • Hole with a hat
  • Induced subgrpah
  • Non-crossing separations

Fingerprint

Dive into the research topics of 'Erdős-Hajnal for cap-free graphs'. Together they form a unique fingerprint.

Cite this