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

Chudnovsky Maria | Zendy; Zwols Yori | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research