The Erdős-Hajnal conjecture for paths and antipaths

DOI10.1016/J.JCTB.2015.01.001MaRDI QIDQ2347853zbMATH OpenOpenAlexFDO

Authors Nicolas Bousquet, A. Lagoutte, Stéphan Thomassé

Publication date 10 June 2015

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

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

zbMATH Keywords

antipathErdős-Hajnal propertypathRamsey-type result

Mathematics Subject Classification ID

Paths and cycles (05C38)

Abstract: We prove that for every k, there exists $c_k>0$ such that every graph G on n vertices not inducing a path $P_k$ and its complement contains a clique or a stable set of size $n^{c_k}$.

Recommendations

• The Erdős-Hajnal conjecture for long holes and antiholes
• Excluding paths and antipaths
• Large cliques or stable sets in graphs with no four-edge path and no five-edge path in the complement
• The Erdős-Hajnal conjecture. A survey
• Erdős–Hajnal for graphs with no 5‐hole

Cites work

• Crossing patterns of semi-algebraic sets
• Density theorems for bipartite graphs and related Ramsey-type results
• Erdős-Hajnal-type results on intersection patterns of geometric objects
• Excluding paths and antipaths
• Graphs with No Induced Five‐Vertex Path or Antipath
• scientific article; zbMATH DE number 1552836 (Why is no real title available?)
• scientific article; zbMATH DE number 4183452 (Why is no real title available?)
• Induced Ramsey-type theorems
• Large cliques or stable sets in graphs with no four-edge path and no five-edge path in the complement
• On universality of graphs with uniformly distributed edges
• Ramsey-type theorems
• Ramsey-type theorems with forbidden subgraphs
• Simplicial vertices in graphs with no induced four-edge path or four-edge antipath, and the \(H_{6}\)-conjecture
• The Erdős-Hajnal conjecture. A survey

Cited in

(34)

• Mangoes and blueberries
• Excluding hooks and their complements
• Vertex-minors and the Erdős-Hajnal conjecture
• Erdős-Hajnal-type results for monotone paths
• Erdős-Hajnal for cap-free graphs
• Pure pairs. II: Excluding all subdivisions of a graph
• Pure pairs. I: Trees and linear anticomplete pairs
• An application of the Gyárfás path argument
• Ordered graphs and large bi-cliques in intersection graphs of curves
• Caterpillars in Erdős-Hajnal
• The Erdős-Hajnal property for graphs with no fixed cycle as a pivot-minor
• Clique-stable set separation in perfect graphs with no balanced skew-partitions
• The Erdős-Hajnal conjecture for long holes and antiholes
• 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
• scientific article; zbMATH DE number 5844324 (Why is no real title available?)
• Clique versus independent set
• A note on the Erdős-Hajnal property for stable graphs
• Metrically homogeneous graphs of diameter \(3\)
• Excluding paths and antipaths
• On the Kőnig‐Egerváry theorem for ‐paths
• scientific article; zbMATH DE number 970798 (Why is no real title available?)
• Large homogeneous submatrices
• A proof of the two-path conjecture
• Strengthening Rödl's theorem
• Large homogeneous subgraphs in bipartite graphs with forbidden induced subgraphs
• Erdős–Hajnal for graphs with no 5‐hole
• Towards the Erdős-Hajnal conjecture for P₅-free graphs
• Graphs of large chromatic number
• A simple \((2 + \epsilon)\)-approximation algorithm for split vertex deletion
• Ordered graphs and large bi-cliques in intersection graphs of curves
• Large cliques or cocliques in hypergraphs with forbidden order-size pairs
• Induced subgraph density. VII: The five-vertex path
• A note on the multicolour version of the Erdős-Hajnal conjecture

This page was built for publication: The Erdős-Hajnal conjecture for paths and antipaths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2347853)