Induced subgraph density. V. All paths approach Erdos-Hajnal

2023/07/27 by Nguyen, Tung, Scott, Alex, Seymour, Paul
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2307.15032

Abstract

The Erdős-Hajnal conjecture says that, for every graph H, there exists c>0 such that every H-free graph on n vertices has a clique or stable set of size at least n^c. In this paper we are concerned with the case when H is a path. The conjecture has been proved for paths with at most five vertices, but not for longer paths. We prove that the conjecture is ``nearly'' true for all paths: for every path H, all H-free graphs with n vertices have cliques or stable sets of size at least 2^(log n)^1-o(1).

Related

• Induced subgraph density. VII. The five-vertex path
• Induced subgraph density. I. A loglog step towards Erdos-Hajnal
• Induced subgraph density. IV. New graphs with the Erdős-Hajnal property
• Towards the Erdős-Hajnal conjecture for P₅-free graphs
• Erdos-Hajnal for graphs with no 5-hole