English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Erd\H{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 atleast $|G|^c$ ("$H$-free" means with no induced subgraph isomorphic to $H$).Alon, Pach, and Solymosi reduced the Erd\H{o}s-Hajnal conjecture to the casewhen $H$ is prime (that is, $H$ cannot be obtained by vertex-substitution fromsmaller graphs); but until now, it was not shown for any prime graph with morethan 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'|\ge 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 theErd\H{o}s-Hajnal conjecture, and infinitely many graphs with this property areprime.  Our proof method also extends to ordered graphs; and we obtain a theoremwhich significantly extends a recent result of Pach and Tomon about excludingmonotone paths.  Indeed, we prove a stronger result, that we can weaken the "$H$-free"hypothesis of the Erd\H{o}s-Hajnal conjecture to one saying that there are notmany 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 theErd\H{o}s-Hajnal conjecture (in tournament form). Say a tournament is buildableif it can be grown from nothing by repeatedly either adding a vertex ofout-degree $\le 1$ or in-degree $\le 1$, or vertex-substitution. All buildabletournaments satisfy the tournament version of the Erd\H{o}s-Hajnal conjecture.

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