The Erdős–Hajnal conjecture for paths and antipaths

International audienceWe prove that for every k, there exists c k > 0 such that every graph G on n vertices with no induced path P k or its complement P k contains a clique or a stable set of size n c k. An n-graph is a graph on n vertices. For every vertex x, N (x) denotes the neighborhood of x, that is the set of vertices y such that xy is an edge. The degree deg(x) is the size of N (x). In this note, we only consider classes of graphs that are closed under induced subgraphs. Moreover a class C is strict if it does not contain all graphs. It is said to have the (weak) Erdős-Hajnal property if there exists some c > 0 such that every graph of C contains a clique or a stable set of size n c where n is the size of G. The Erdős-Hajnal conjecture [8] asserts that every strict class of graphs has the Erdős-Hajnal property; see [3] for a survey. This fascinating question is open even for graphs not inducing a cycle of length five. When excluding a single graph H, Alon, Pach and Solymosi showed in [2] that it suffices to consider prime H, namely graphs without nontrivial modules (a module is a subset V of vertices such that for every x, y ∈ V , N (x) \ V = N (y) \ V). A natural approach is then to study classes of graphs with intermediate difficulty, hoping to get a proof scheme which could be extended. A natural prime candidate to forbid is certainly the path. Unfortunately, even excluding the path on five vertices seems already hard. Chudnovsky and Zwols studied the class C k of graphs not inducing the path P k on k vertices or its complement P k. They proved the Erdős-Hajnal property for P 5 and P 6-free graphs [7]. This was extended for P 5 and P 7-free graphs by Chudnovsky and Seymour [6]. Moreover structural results have been provided for C 5 [4, 5]. We show in this note that for every fixed k, the class C k has the Erdős-Hajnal property. An n-graph is an ε-stable set if it has at most ε n