Induced subgraphs density. IV. New graphs with the Erd\H{o}s-Hajnal property

arXiv2307.06455MaRDI QIDQ6511053FDOQ6511053

Authors: Tung D. Nguyen, Alex Scott, Paul Seymour 

Abstract: ErdH{o}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$ ("$H$-free" means with no induced subgraph isomorphic to $H$). Alon, Pach, and Solymosi reduced the ErdH{o}s-Hajnal conjecture to the case when $H$ is 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^{\prime }$ with $|G^{\prime }|ge3$, $G^{\prime }$ has a vertex of degree one and a vertex of degree $|G^{\prime }|-2$. We will prove that every graph $H$ with this property satisfies the ErdH{o}s-Hajnal conjecture, and infinitely many graphs with this property are prime. Our proof method also extends to ordered graphs; and we obtain a theorem which significantly extends a recent result of Pach and Tomon about excluding monotone paths. Indeed, we prove a stronger result, that we can weaken the "$H$-free" hypothesis of the ErdH{o}s-Hajnal conjecture to one saying that there are not many copies of $H$; and strengthen its conclusion, deducing a "polynomial" version of R"odl's theorem conjectured by Fox and Sudakov. We also obtain infinitely many new prime tournaments that satisfy the ErdH{o}s-Hajnal conjecture (in tournament form). Say a tournament is buildable if it can be grown from nothing by repeatedly either adding a vertex of out-degree $le1$ or in-degree $le1$, or vertex-substitution. All buildable tournaments satisfy the tournament version of the ErdH{o}s-Hajnal conjecture.

This page was built for publication: Induced subgraphs density. IV. New graphs with the Erd\H{o}s-Hajnal property

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