Premium
Large cliques or stable sets in graphs with no four‐edge path and no five‐edge path in the complement
Author(s) -
Chudnovsky Maria,
Zwols Yori
Publication year - 2012
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20626
Subject(s) - combinatorics , mathematics , induced path , block graph , conjecture , induced subgraph , path graph , split graph , independent set , discrete mathematics , complement (music) , graph factorization , graph , path (computing) , longest path problem , chordal graph , pathwidth , line graph , graph power , computer science , vertex (graph theory) , biochemistry , chemistry , complementation , programming language , gene , phenotype
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 n 1/6 . © 2011 Wiley Periodicals, Inc. J Graph Theory