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

DOI10.1002/jgt.20626zbMath1247.05151OpenAlexW1595412293MaRDI QIDQ2911494

Maria Chudnovsky, Yori Zwols

Publication date: 31 August 2012

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.20626

zbMATH Keywords

forbidden induced subgraphsErdős-Hajnal conjecture

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (8)

Towards the Erdős-Hajnal conjecture for \(P_5\)-free graphs ⋮ Erdős-Hajnal for cap-free graphs ⋮ Excluding paths and antipaths ⋮ Erdős-Hajnal-type theorems in hypergraphs ⋮ Pure pairs. II: Excluding all subdivisions of a graph ⋮ The Erdös--Hajnal Conjecture for Long Holes and Antiholes ⋮ The Erdős-Hajnal conjecture for paths and antipaths ⋮ The Erdös-Hajnal Conjecture-A Survey

Cites Work

• The strong perfect graph theorem
• The Erdős-Hajnal conjecture for bull-free graphs
• Normal hypergraphs and the perfect graph conjecture. (Reprint)
• Ramsey-type theorems with forbidden subgraphs

This page was built for publication: Large cliques or stable sets in graphs with no four-edge path and no five-edge path in the complement