Erdős-Hajnal for cap-free graphs

DOI10.1016/j.jctb.2021.07.006zbMath1473.05220OpenAlexW3187598484MaRDI QIDQ1984528

Maria Chudnovsky, P. D. Seymour

Publication date: 16 September 2021

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2021.07.006

zbMATH Keywords

capinduced subgraphErdős-Hajnal conjecturehole with a hatnon-crossing separations

Mathematics Subject Classification ID

Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Distance in graphs (05C12) Generalized Ramsey theory (05C55) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Ramsey theory (05D10)

Related Items (2)

Erdős–Hajnal for graphs with no 5‐hole ⋮ Towards the Erdős-Hajnal conjecture for \(P_5\)-free graphs

Cites Work

• Excluding paths and antipaths
• Ramsey-type theorems
• The strong perfect graph theorem
• The Erdős-Hajnal conjecture for bull-free graphs
• On universality of graphs with uniformly distributed edges
• Towards Erdős-Hajnal for graphs with no 5-hole
• The Erdős-Hajnal conjecture for paths and antipaths
• Normal hypergraphs and the perfect graph conjecture
• The Erdös--Hajnal Conjecture for Long Holes and Antiholes
• Large cliques or stable sets in graphs with no four-edge path and no five-edge path in the complement
• Even and odd holes in cap-free graphs
• Ramsey-type theorems with forbidden subgraphs
• Unnamed Item
• Unnamed Item

This page was built for publication: Erdős-Hajnal for cap-free graphs