The Erdös--Hajnal Conjecture for Long Holes and Antiholes

DOI10.1137/140981745zbMath1338.05196arXiv1408.1964OpenAlexW1589979193WikidataQ123002505 ScholiaQ123002505MaRDI QIDQ2813338

Marthe Bonamy, Steéphan Thomassé, Nicolas Bousquet

Publication date: 23 June 2016

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1408.1964

zbMATH Keywords

holesstable setclique

Mathematics Subject Classification ID

Paths and cycles (05C38) Generalized Ramsey theory (05C55) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (12)

Weighted Rooted Trees: Fat or Tall? ⋮ The Erdős-Hajnal property for graphs with no fixed cycle as a pivot-minor ⋮ Excluding hooks and their complements ⋮ Erdős–Hajnal for graphs with no 5‐hole ⋮ Towards the Erdős-Hajnal conjecture for \(P_5\)-free graphs ⋮ Decomposition techniques applied to the clique-stable set separation problem ⋮ Pure pairs. I: Trees and linear anticomplete pairs ⋮ Erdős-Hajnal for cap-free graphs ⋮ On low rank-width colorings ⋮ A note on weighted rooted trees ⋮ Pure pairs. II: Excluding all subdivisions of a graph ⋮ Submodular functions and rooted trees

Cites Work

• Unnamed Item
• Unnamed Item
• Excluding paths and antipaths
• Ramsey-type theorems
• The Erdős-Hajnal conjecture for bull-free graphs
• On universality of graphs with uniformly distributed edges
• Forcing large transitive subtournaments
• The Erdős-Hajnal conjecture for paths and antipaths
• A note on weighted rooted trees
• Crossing patterns of semi-algebraic sets
• The Erdös-Hajnal Conjecture-A Survey
• Large cliques or stable sets in graphs with no four-edge path and no five-edge path in the complement
• Induced Ramsey-type theorems
• Ramsey-type theorems with forbidden subgraphs

This page was built for publication: The Erdös--Hajnal Conjecture for Long Holes and Antiholes