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

DOI10.1007/S40687-023-00413-YzbMATH Open1530.05091arXiv2210.10755OpenAlexW4389948002MaRDI QIDQ6138779FDOQ6138779

Authors: Pablo J. Blanco, Matija Bucić 

Publication date: 16 January 2024

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

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.

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

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

zbMATH Keywords

Erdős-Hajnal conjecture

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Cites Work

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

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)