The Erdős–Hajnal Theorems for the E-Graph and Bird

Given: The $E$-graph on $\{p_1,\dots ,p_5,q\}$, the Bird graph on $\{x_1,x_2,x_3,y,z,w\}$, and the bull on $\{x_1,x_2,x_3,y,z\}$.

The $E$-graph has edge set $\{p_1{p}_2,p_2{p}_3,p_3{p}_4,p_4{p}_5,p_{3}q\}$ and co-$E$ is its complement (The $E$-graph and co-$E$).

The Bird graph has edge set $\{x_1{x}_2,x_2{x}_3,x_1{x}_3,x_{1}y,x_{2}z,yw\}$ and co-Bird is its complement (The Bird graph and co-Bird).

The bull has vertex set $\{x_1,x_2,x_3,y,z\}$ and edge set $\{x_1{x}_2,x_2{x}_3,x_1{x}_3,x_{1}y,x_{2}z\}$ (The bull graph).

The path graph $P_5$ has vertices $0,1,2,3,4$ and edges $\{i,i+1\}$ for $0\le i<4$, and no others (Empty and complete graphs, complete bipartite graphs, and the convention that $P_n$ and $C_n$ have $n$ vertices).

A finite family $\mathcal{F}$ is leaf-reducible when some $H\in \mathcal{F}$ has a leaf $v$ and the modified family $\{H\setminus \{v\}\}\cup (\mathcal{F}\setminus \{H\})$ has the Erdős-Hajnal property in the family sense (Leaf-reducible finite graph families).

A vertex of degree one is a leaf; deletion $H\setminus \{v\}$ is the subgraph induced by $V(H)\setminus \{v\}$ (Trees, forests, leaves and isolated vertices, Subgraphs, induced subgraphs and spanning subgraphs).

A graph isomorphism is a bijection preserving adjacency and nonadjacency, and an induced embedding of $H$ in $G$ is an injection preserving adjacency and nonadjacency on distinct pairs (Graph isomorphisms, automorphisms and graph complements, Induced embeddings and induced copies of a graph).

A graph is $H$-free when it has no induced copy of $H$, and $\mathcal{F}$-free means $H$-free for every $H\in \mathcal{F}$ ($H$-free and $\mathcal{F}$-free graphs under the induced-subgraph convention).

The graph $P_5$ has the Erdős-Hajnal property (The five-vertex path and its complement have the Erdős-Hajnal property).

The bull graph has the Erdős-Hajnal property (The bull graph has the Erdős-Hajnal property).

A graph $H$ has the Erdős-Hajnal property when the hereditary class of $H$-free graphs has an Erdős-Hajnal constant, and the same terminology applies to a finite family through its class of family-free graphs (The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class).

Given: The singleton family $\{E\}$ and the complement family $\overline{\{E\}}=\{\mathrm{c}\mathrm{o}\text{-}E\}$ of the published generalized-niceness convention.

The singleton family $\{E\}$ has property $(\ast )$ (The singleton family $\{E\}$ has property (*)).

The family $\{H_5,\mathrm{c}\mathrm{o}\text{-}E\}$ has the Erdős-Hajnal property, so it has an Erdős-Hajnal constant (The family consisting of $H_5$ and co-$E$ has the Erdős–Hajnal property).

Leaf/co-leaf transfer: if $\mathcal{F}$ is a finite family, $H_1\in \mathcal{F}$ has a leaf $v$, $H_2\in \mathcal{F}$ has a co-leaf $w$, and the two modified families are $\{H_1\setminus \{v\}\}\cup (\mathcal{F}\setminus \{H_1\})$ and $\{H_2\setminus \{w\}\}\cup (\mathcal{F}\setminus \{H_2\})$, then the Erdős-Hajnal property of both modified families implies it for $\mathcal{F}$ (Deleting a leaf and a co-leaf preserves the Erdős-Hajnal property of a finite forbidden family).

In every co-$E$-free graph, every special-vertex comb of the property-$(\ast )$ trigger admits the $\{H_5,\mathrm{c}\mathrm{o}\text{-}E\}$ structural partition: each block splits as $B_i=X_i\cup Y_i$ with $Y_i$ $\{H_5,\mathrm{c}\mathrm{o}\text{-}E\}$-free and $X_i$ carrying a nonempty-block pure blockade partition whose pattern is $\{H_5,\mathrm{c}\mathrm{o}\text{-}E\}$-free and whose blocks are pure to every vertex of the other comb blocks (A special-vertex comb in a co-$E$-free graph admits the $\{H_5,\mathrm{c}\mathrm{o}\text{-}E\}$ structural partition).

Special-vertex-local criterion: if finite families ${\mathcal{F}}_1,{\mathcal{F}}_2$ have a common Erdős-Hajnal constant $c\in (0,1]$ and every special-vertex comb in every $\bar{\mathcal{H}}$-free graph admits a partition with clauses (1) and (2.1)--(2.3) of the structural comb partition, then $\mathcal{H}$ has property $(\ast )$ (The special-vertex-local structural-partition criterion implies property (*)).

If a finite family has property $(\ast )$ and is leaf-reducible, then it is generalized nice (Property (*) and leaf reducibility imply generalized niceness).

The singleton family $\{E\}$ is leaf-reducible (The $E$-graph and Bird singleton families are leaf-reducible).

Generalized niceness of a finite family $\mathcal{F}$ is the four-outcome schema quantified over $\bar{\mathcal{F}}$-free graphs (Generalized nice finite graph families).

Property $(\ast )$ for a finite family $\mathcal{F}$ is a condition on $\bar{\mathcal{F}}$-free graphs carrying the special-vertex comb trigger (Property (*) for a finite graph family).

The $E$-graph has edge set $\{p_1{p}_2,p_2{p}_3,p_3{p}_4,p_4{p}_5,p_{3}q\}$ on six vertices, and co-$E$ is its complement (The $E$-graph and co-$E$).

A vertex $v$ is a co-leaf of a graph $G$ when ${\mathrm{deg}}_G(v)=\mathrm{\mid }V(G)\mathrm{\mid }-2$, equivalently when $v$ is adjacent to every other vertex except one (Co-leaves of a finite graph).

If $ϵ$ is an Erdős-Hajnal constant for a hereditary class and $0<\delta \le ϵ$, then $\delta$ is one too (Every smaller positive exponent is again an Erdős–Hajnal constant).

Given: The singleton family $\{E\}$ and its class of $E$-free finite graphs.

The singleton family $\{E\}$ is generalized nice (The singleton $E$-graph family is generalized nice).

The singleton family $\{E\}$ is leaf-reducible; deleting the leaf $q$ from $E$ gives $P_5$, and the reduced singleton family has the Erdős-Hajnal property (The $E$-graph and Bird singleton families are leaf-reducible).

The singleton family $\{E\}$ is wonderful (The $E$-graph and the Bird graph are wonderful).

Every generalized nice, leaf-reducible, wonderful finite family has the Erdős-Hajnal property (Leaf-reducible wonderful generalized nice finite families have the Erdős-Hajnal property).

A positive real $ϵ$ is an Erdős-Hajnal constant for a hereditary class $\mathcal{C}$ when every nonempty $G\in \mathcal{C}$ satisfies $\mathrm{hom}(G)\ge \mathrm{\mid }V(G){\mathrm{\mid }}^{ϵ}$; a graph $H$ has the Erdős-Hajnal property when its class of $H$-free graphs has such a constant, and $\mathrm{hom}(G)=\max \{\omega (G),\alpha (G)\}$ is the size of the largest clique or stable set of $G$ (The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class, Homogeneous vertex sets and the homogeneous number $\mathrm{hom}(G)=\max \{\omega (G),\alpha (G)\}$).

Graph $G$ is $H$-free when it has no induced copy of $H$ ($H$-free and $\mathcal{F}$-free graphs under the induced-subgraph convention), and the class of $H$-free graphs is hereditary for every finite graph $H$ (Every class defined by forbidden induced subgraphs is hereditary).

The $E$-graph is the six-vertex graph with edge set $\{p_1{p}_2,p_2{p}_3,p_3{p}_4,p_4{p}_5,p_{3}q\}$ (The $E$-graph and co-$E$).

Given: An arbitrary co-Bird-free finite graph $G$ and an arbitrary special-vertex comb in it, with special vertex $v$ complete to ${\bigcup }_i{B}_i$ and anticomplete to the teeth $\{a_i\}$.

The $E$-graph has the Erdős-Hajnal property: there is ${ϵ}_E>0$ such that every nonempty $E$-free graph has a clique or stable set of size at least $\mathrm{\mid }V(G){\mathrm{\mid }}^{{ϵ}_E}$ (The $E$-graph has the Erdős-Hajnal property).

Every positive exponent below an Erdős-Hajnal constant of a hereditary class is again one (Every smaller positive exponent is again an Erdős–Hajnal constant).

Let $((a_k,B_k):k\in [\mathrm{\ell }])$ be an $(\mathrm{\ell },w)$-comb in a finite simple co-Bird-free graph $G$, and let $v$ be outside all teeth and blocks, complete to every $B_k$ and anticomplete to every tooth. For every $i$ there are disjoint sets $X_i,Y_i$ with $B_i=X_i\cup Y_i$ such that $G[Y_i]$ is $E$-free, and $X_i$ has a partition into a nonempty ordered sequence $(A_1^i,\dots ,A_{t_i}^i)$ of nonempty sets that is a pure blockade, whose pattern is $E$-free, and such that each individual vertex of every other comb block is pure to each $A_j^i$ (A special-vertex co-Bird-free comb admits an E-free structural partition).

Special-vertex-local criterion: let ${\mathcal{F}}_1,{\mathcal{F}}_2$ have a common Erdős-Hajnal constant $c\in (0,1]$. Suppose that, in every $\bar{\mathcal{H}}$-free graph, every special-vertex comb occurring in the definition of property $(\ast )$ has a partition satisfying clauses (1) and (2.1)--(2.3) of the structural comb partition. Then $\mathcal{H}$ has property $(\ast )$ (The special-vertex-local structural-partition criterion implies property (*)).

Property $(\ast )$ for a finite family $\mathcal{F}$ asks, for every $\bar{\mathcal{F}}$-free graph containing an $(\mathrm{\ell },w)$-comb with $\mathrm{\ell },w\ge 4$ and a vertex $v$ outside all teeth and blocks complete to ${\bigcup }_i{B}_i$ and anticomplete to $\{a_i\}$, that one of three listed outcomes hold with constants $c_1,c_2,c_3>0$ (Property (*) for a finite graph family).

The structural comb-partition clauses are: (1) $Y_i$ is ${\mathcal{F}}_1$-free; (2) $X_i$ has a nonempty-block pure-blockade partition whose pattern graph is ${\mathcal{F}}_2$-free; (3) every vertex of ${\bigcup }_{k\mathrm{\ne }i}{B}_k$ is pure to every block of that partition (The structural comb-partition hypothesis).

The Bird graph has vertex set $\{x_1,x_2,x_3,y,z,w\}$ and edge set $\{x_1{x}_2,x_2{x}_3,x_1{x}_3,x_{1}y,x_{2}z,yw\}$, and co-Bird is its complement (The Bird graph and co-Bird).

The $E$-graph has edge set $\{p_1{p}_2,p_2{p}_3,p_3{p}_4,p_4{p}_5,p_{3}q\}$, and co-$E$ is its complement (The $E$-graph and co-$E$).

A graph is $H$-free when it has no induced copy of $H$, and $\mathcal{F}$-free when it is $H$-free for every $H\in \mathcal{F}$ ($H$-free and $\mathcal{F}$-free graphs under the induced-subgraph convention).

A graph $H$ has the Erdős-Hajnal property when its class of $H$-free graphs has an Erdős-Hajnal constant, and the same applies to a finite family through its family-free class (The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class).

Given: The singleton family $\{\mathrm{B}\mathrm{i}\mathrm{r}\mathrm{d}\}$.

The singleton family $\{\mathrm{B}\mathrm{i}\mathrm{r}\mathrm{d}\}$ has property $(\ast )$, with its special-vertex comb trigger in co-Bird-free graphs (The singleton Bird family has property (*)).

The singleton family $\{\mathrm{B}\mathrm{i}\mathrm{r}\mathrm{d}\}$ is leaf-reducible: deleting the added leaf $w$ from Bird gives the bull, and the reduced singleton family has the Erdős-Hajnal property (The $E$-graph and Bird singleton families are leaf-reducible).

If a finite family has property $(\ast )$ and is leaf-reducible, then it is generalized nice (Property (*) and leaf reducibility imply generalized niceness).

Generalized niceness of a finite family $\mathcal{F}$ is the four-outcome schema quantified over $\bar{\mathcal{F}}$-free graphs (Generalized nice finite graph families).

Property $(\ast )$ for a finite family $\mathcal{F}$ is a condition on $\bar{\mathcal{F}}$-free graphs, and leaf-reducibility asks that deleting one leaf from one member produce a family with the Erdős-Hajnal property (Property (*) for a finite graph family, Leaf-reducible finite graph families).

co-Bird is the complement of the Bird graph (The Bird graph and co-Bird).

Given: The singleton family $\{\mathrm{B}\mathrm{i}\mathrm{r}\mathrm{d}\}$ and its class of Bird-free finite graphs.

The singleton family $\{\mathrm{B}\mathrm{i}\mathrm{r}\mathrm{d}\}$ is generalized nice (The singleton Bird family is generalized nice).

The singleton family $\{\mathrm{B}\mathrm{i}\mathrm{r}\mathrm{d}\}$ is leaf-reducible; deleting the added leaf $w$ gives the bull, and the reduced singleton family has the Erdős-Hajnal property (The $E$-graph and Bird singleton families are leaf-reducible).

The singleton family $\{\mathrm{B}\mathrm{i}\mathrm{r}\mathrm{d}\}$ is wonderful (The $E$-graph and the Bird graph are wonderful).

Every generalized nice, leaf-reducible, wonderful finite family has the Erdős-Hajnal property (Leaf-reducible wonderful generalized nice finite families have the Erdős-Hajnal property).

A positive real $ϵ$ is an Erdős-Hajnal constant for a hereditary class $\mathcal{C}$ when every nonempty $G\in \mathcal{C}$ satisfies $\mathrm{hom}(G)\ge \mathrm{\mid }V(G){\mathrm{\mid }}^{ϵ}$; a graph $H$ has the Erdős-Hajnal property when its class of $H$-free graphs has such a constant, and $\mathrm{hom}(G)=\max \{\omega (G),\alpha (G)\}$ is the size of the largest clique or stable set of $G$ (The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class, Homogeneous vertex sets and the homogeneous number $\mathrm{hom}(G)=\max \{\omega (G),\alpha (G)\}$).

Graph $G$ is $H$-free when it has no induced copy of $H$ ($H$-free and $\mathcal{F}$-free graphs under the induced-subgraph convention), and the class of $H$-free graphs is hereditary for every finite graph $H$ (Every class defined by forbidden induced subgraphs is hereditary).

The Bird graph has vertex set $\{x_1,x_2,x_3,y,z,w\}$ and edge set $\{x_1{x}_2,x_2{x}_3,x_1{x}_3,x_{1}y,x_{2}z,yw\}$ (The Bird graph and co-Bird).