2023/07/12 by Tung Nguyen, Nguyen, Tung, Alex Scott +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2307.06455
openalex publication_date 2023/07/12 · openalex created_date 2023/07/15 · openalex updated_date 2026/07/28
Erdős and Hajnal conjectured that for every graph H, there exists c>0 such that every H-free graph G has a clique or a stable set of size at least |G|c (a graph is H-free if it has no induced subgraph isomorphic to H). Alon, Pach, and Solymosi reduced the Erdős-Hajnal conjecture to the case when H is \em prime (that is, H cannot be obtained by vertex-substitution from smaller graphs); but until now, it was not shown for any prime graph with more than five vertices. We will provide infinitely many prime graphs that satisfy the conjecture. Let H be a graph with the property that for every prime induced subgraph G' with |G'|≥ 3, G' has a vertex of degree one and a vertex of degree |G'|-2. We will prove that every graph H with this property satisfies the Erdős-Hajnal conjecture, and infinitely many graphs with this property are prime. More generally, say a graph is \em buildable if every prime induced subgraph with at least three vertices has a vertex of degree one. We prove that if H1 and H2 are buildable, there exists c>0 such that every graph G that is both H1-free and H2-free has a clique or a stable set of size at least |G|c. Our proof uses a new technique of ``iterative sparsification'', where we pass to a sequence of successively more restricted induced subgraphs. This approach also extends to ordered graphs and to tournaments. For ordered graphs, we obtain a theorem which significantly extends a recent result of Pach and Tomon about excluding monotone paths; and for tournaments, we obtain infinitely many new prime tournaments that satisfy the Erdős-Hajnal conjecture (in tournament form).