Large cliques or stable sets in graphs with no four-edge path and no five-edge path in the complement

Maria Chudnovsky, Yori Zwols

Research output: Contribution to journalArticle

4 Scopus citations

Abstract

Erdös and Hajnal [Discrete Math 25 (1989), 37-52] conjectured that, for any graph H, every graph on n vertices that does not have H as an induced subgraph contains a clique or a stable set of size nε(H) for some ε(H)>0. The Conjecture 1. known to be true for graphs H with |V(H)|<4. One of the two remaining open cases on five vertices is the case where H is a four-edge path, the other case being a cycle of length five. In this article we prove that every graph on n vertices that does not contain a four-edge path or the complement of a five-edge path as an induced subgraph contains either a clique or a stable set of size at least n1/6.

Original languageEnglish (US)
Pages (from-to)449-472
Number of pages24
JournalJournal of Graph Theory
Volume70
Issue number4
DOIs
StatePublished - Jan 1 2012
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • Erdös-Hajnal conjecture
  • forbidden induced subgraphs

Fingerprint Dive into the research topics of 'Large cliques or stable sets in graphs with no four-edge path and no five-edge path in the complement'. Together they form a unique fingerprint.

  • Cite this