Towards the Erdős-Hajnal conjecture for P₅-free graphs

DOI10.1007/S40687-023-00413-YMaRDI QIDQ6138779zbMATH OpenOpenAlexFDO

Authors Pablo J. Blanco, Matija Bucić

Publication date 16 January 2024

Published in Research in the Mathematical Sciences (Search for Journal in Brave)

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

zbMATH Keywords

Erdős-Hajnal conjecture

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Abstract: The ErdH{o}s-Hajnal conjecture is one of the most classical and well-known problems in extremal and structural combinatorics dating back to 1977. It asserts that in stark contrast to the case of a general $n$-vertex graph if one imposes even a little bit of structure on the graph, namely by forbidding a fixed graph $H$ as an induced subgraph, instead of only being able to find a polylogarithmic size clique or an independent set one can find one of polynomial size. Despite being the focus of considerable attention over the years the conjecture remains open. In this paper we improve the best known lower bound of $2^{Omega(sqrtlogn)}$ on this question, due to ErdH{o}s and Hajnal from 1989, in the smallest open case, namely when one forbids a $P_5$, the path on $5$ vertices. Namely, we show that any $P_5$-free $n$ vertex graph contains a clique or an independent set of size at least $2^{Omega(logn{)}^{2/3}}$. Our methods also lead to the same improvement for an infinite family of graphs.

Recommendations

• Towards Erdős-Hajnal for graphs with no 5-hole
• Erdős–Hajnal for graphs with no 5‐hole
• The Erdős-Hajnal conjecture for paths and antipaths
• Large cliques or stable sets in graphs with no four-edge path and no five-edge path in the complement
• Induced subgraph density. I: A loglog step towards Erdős-Hajnal

Cites work

• scientific article; zbMATH DE number 3628985 (Why is no real title available?)
• scientific article; zbMATH DE number 970798 (Why is no real title available?)
• Crossing patterns of semi-algebraic sets
• Erdős-Hajnal for cap-free graphs
• Erdős-Hajnal-type results for monotone paths
• Erdős-Hajnal-type results on intersection patterns of geometric objects
• Erdős–Hajnal for graphs with no 5‐hole
• Excluding paths and antipaths
• Large cliques or stable sets in graphs with no four-edge path and no five-edge path in the complement
• On a property of the class of n-colorable graphs
• Polynomial bounds for chromatic number. IV: A near-polynomial bound for excluding the five-vertex path
• Pure pairs. I: Trees and linear anticomplete pairs
• Pure pairs. II: Excluding all subdivisions of a graph
• Pure pairs. III. Sparse graphs with no polynomial‐sized anticomplete pairs
• Ramsey-type theorems
• Ramsey-type theorems with forbidden subgraphs
• The Erdős-Hajnal conjecture for bull-free graphs
• The Erdős-Hajnal conjecture for long holes and antiholes
• The Erdős-Hajnal conjecture for paths and antipaths
• The probabilistic method
• Towards Erdős-Hajnal for graphs with no 5-hole

Cited in

(1)

• Hitting all maximum stable sets in \(P_5\)-free graphs

This page was built for publication: Towards the Erdős-Hajnal conjecture for \(P_5\)-free graphs

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