Star Expansions and the Erdős-Hajnal Property

By [F1], choose vertices $x_i\in B_i$ for every $i\in [m]$. Let $X:=\{x_1,\dots ,x_m\}$. Because the blocks are pairwise disjoint, these $m$ vertices are distinct.

For distinct $i,j\in [m]$, the hypothesis says that $x_i$ and $x_j$ are adjacent exactly when $u_i$ and $u_j$ are adjacent in $F$. Hence the map $u_i\mapsto x_i$ is an adjacency-preserving and nonadjacency-preserving bijection from $V(F)$ to $X$, so $G[X]$ is an induced copy of $F$.

The copy $G[X]$ lies in $V(\mathcal{B})$ and uses exactly one vertex from each block, so [L1] shows that it is $\mathcal{B}$-rainbow.

Apply [L1] with parameter $ϵ\mathrm{/}4$ and let $\delta :={\delta }_0\mathrm{/}2$. Then there is a set $Z\subseteq V(G)$ with $\mathrm{\mid }Z\mathrm{\mid }\ge 2\delta \mathrm{\mid }V(G)\mathrm{\mid }$ such that either $G[Z]$ or $\bar{G}[Z]$ is $(ϵ\mathrm{/}4)$-sparse.

Let $m:=\lceil \delta \mathrm{\mid }V(G)\mathrm{\mid }\rceil$. Since $\mathrm{\mid }Z\mathrm{\mid }\ge 2\delta \mathrm{\mid }V(G)\mathrm{\mid }$, we have $m\le (\mathrm{\mid }Z\mathrm{\mid }+1)\mathrm{/}2$. Applying [L2] inside the sparse side on $Z$ gives $X\subseteq Z$ with $\mathrm{\mid }X\mathrm{\mid }=m\ge \delta \mathrm{\mid }V(G)\mathrm{\mid }$ such that the same side has maximum degree at most $4(ϵ\mathrm{/}4)(m-1)\le ϵ\mathrm{\mid }X\mathrm{\mid }$.

Thus one of $G[X]$ or $\bar{G}[X]$ has maximum degree at most $ϵ\mathrm{\mid }X\mathrm{\mid }$, as required.

The cited source theorem combines the bounded-degree consequence [L2] with the rainbow-copy criterion [L1] and produces constants $d>0$ and $K$ such that any blockade of length at least $K$ and width $W$ either contains a pure pair $A,B$ with $\mathrm{\mid }A\mathrm{\mid },\mathrm{\mid }B\mathrm{\mid }\ge W\mathrm{/}d$ or has a blockade-rainbow copy of one of $F,\bar{F}$.

Taking $r:=K$ and $\sigma :=1\mathrm{/}d$, and viewing a pure pair as a pure subblockade of length $2$ and width at least $\sigma \mathrm{width}(\mathcal{B})$, converts the source conclusion into exactly conclusions 1, 2, and 3 above.

Therefore the present statement follows.

The cited source theorem proves exactly this cograph-pattern or rainbow-copy alternative after translating its pattern language into the library's blockade notation.

Therefore the present statement follows.

The cited proof chooses the forest/blockade constants first and then chooses the critical exponent so the cograph-pattern blockade has the exact width required by the criticality theorem.

The alternative rainbow outcome supplies one of the four forbidden star-expansion graphs, while the quantitatively wide cograph outcome contradicts criticality. The source therefore proves exactly the stated four-family Erdős-Hajnal property.

Apply [L1] with $F:=P_4$. Because $P_4$ is a forest, the family $\{P_4^{\star },(\overline{P_4}{)}^{\star },\overline{P_4^{\star }},\overline{(\stackrel{‾}{P_4}{)}^{\star }}\}$ has the Erdős-Hajnal property.

By [F1], $P_4\cong \overline{P_4}$, so $(\overline{P_4}{)}^{\star }\cong P_4^{\star }$ and $\overline{(\stackrel{‾}{P_4}{)}^{\star }}\cong \overline{P_4^{\star }}$. Hence the four-family in step 1.1 collapses to the two-family $\{P_4^{\star },\overline{P_4^{\star }}\}$.

Therefore the star-expansion of $P_4$ and its complement have the Erdős-Hajnal property.

Consider the six vertices $v,a_1,b_1,b_2,b_3,a_3$. By [L1], the edges among them are exactly $v{a}_1,a_1{b}_1,b_1{b}_2,b_2{b}_3,b_3{a}_3,a_{3}v$. No other edge is present: the teeth $a_1,a_3$ meet only their matched path vertices and the root, and the path contains no edge $b_1{b}_3$. Hence these six vertices induce a $6$-cycle.

Consider the seven vertices $v,a_1,b_1,b_2,b_3,b_4,a_4$. Again [L1] shows that the edges among them are exactly $v{a}_1,a_1{b}_1,b_1{b}_2,b_2{b}_3,b_3{b}_4,b_4{a}_4,a_{4}v$. No chord occurs: $a_1$ and $a_4$ meet only the root and their matched path vertices, and the path has no edges other than the consecutive ones displayed. Hence these seven vertices induce a $7$-cycle.

Steps 1.1 and 1.2 give induced copies of $C_6$ and $C_7$ in $P_4^{\star }$.

Let $\mathcal{C}$ be the class of graphs containing neither $C_6$ nor $\overline{C_6}$ as an induced subgraph. If $G\in \mathcal{C}$ contained $P_4^{\star }$, then [L2] would force an induced $C_6$ in $G$; similarly, if $G$ contained $\overline{P_4^{\star }}$, then $\bar{G}$ would contain $P_4^{\star }$ and hence $G$ would contain $\overline{C_6}$. Thus every graph in $\mathcal{C}$ is also $\{P_4^{\star },\overline{P_4^{\star }}\}$-free.

Therefore $\mathcal{C}$ is a hereditary subclass of the class from [L1], so [L3] implies that $\mathcal{C}$ has the Erdős-Hajnal property. This is exactly the statement that $\{C_6,\overline{C_6}\}$ has the Erdős-Hajnal property.

Let $\mathcal{C}$ be the class of graphs containing neither $C_7$ nor $\overline{C_7}$ as an induced subgraph. The same containment argument as in the $C_6$ case, now using [L2], shows that every graph in $\mathcal{C}$ is $\{P_4^{\star },\overline{P_4^{\star }}\}$-free.

Applying [L3] to the superclass from [L1], we conclude that $\mathcal{C}$ has the Erdős-Hajnal property. Equivalently, $\{C_7,\overline{C_7}\}$ has the Erdős-Hajnal property.

The cited primary-source theorem treats the complement-side low-degree case separately, using the forest-free sparse-pair theorem, and treats the graph-side case with the quantitative comb construction.

Its two cases exclude a critical counterexample and yield exactly the Erdős-Hajnal property for $\{\bar{F},F^{\star }\}$.

Consider the vertex set $\{v,a_1,b_1,\dots ,b_{r+1},a_{r+1}\}$. Along this set the displayed edges $v{a}_1,a_1{b}_1,b_1{b}_2,\dots ,b_r{b}_{r+1},b_{r+1}{a}_{r+1},a_{r+1}v$ form a cycle of length $r+4$.

No other edge joins two vertices of this set. The forest path contributes only the consecutive edges $b_i{b}_{i+1}$, since it is induced in $F$, and [L1] shows that $a_1$ and $a_{r+1}$ meet only their matched path vertices and the root. Hence the chosen vertices induce exactly that cycle.

Therefore $F^{\star }$ contains an induced cycle on $r+4$ vertices.

Choose a forest $H$ that contains $F$ as an induced subgraph and also contains an induced path on $\mathrm{\ell }-3$ vertices. For instance, take the disjoint union of $F$ with a path long enough to realize that length. By [L2], the star-expansion $H^{\star }$ contains an induced copy of $C$.

If a graph $G$ is $C$-free and $\bar{F}$-free, then it is also $H^{\star }$-free and $\bar{H}$-free. Indeed, an induced copy of $H^{\star }$ would contain the induced cycle $C$ from step 1.1, and an induced copy of $\bar{H}$ would contain $\bar{F}$ because $F$ is an induced subgraph of $H$. Thus the class forbidding $\{C,\bar{F}\}$ is a hereditary subclass of the class forbidding $\{H^{\star },\bar{H}\}$.

By [L1], the larger class from step 2.1 has the Erdős-Hajnal property, so [L3] passes that property to the subclass forbidding $\{C,\bar{F}\}$.

For each $i$, choose a connected component $D_i$ of $G[B_i]$. Since $D_i\subseteq B_i$ and the comb blocks are pairwise disjoint, the sequence $(D_1,\dots ,D_t)$ is again a blockade after deleting any empty choices, and we may choose every $D_i$ nonempty.

Fix distinct indices $i,j$. Suppose some vertex $u\in D_j$ is mixed on $D_i$. Since $G[D_i]$ is connected, there is an edge $xy$ of $G[D_i]$ such that $u$ is adjacent to $x$ and not to $y$. By [L1], among the six vertices $v,a_i,a_j,x,y,u$ the edges $v{a}_i,v{a}_j,a_{i}x,a_{i}y,ux,u{a}_j,xy$ are present, while $vu,vy,x{a}_j,y{a}_j,u{a}_i,uy,a_i{a}_j$ are absent. Hence $v-a_j-u-x-a_i-v$ is a five-cycle, and $y$ is adjacent exactly to the adjacent cycle vertices $x,a_i$. Therefore these six vertices induce a hatted five-cycle, contradicting the hypothesis. So no vertex of $D_j$ is mixed on $D_i$; swapping $i$ and $j$ gives the converse direction, and therefore each pair $(D_i,D_j)$ is either complete or anticomplete.

Since every pair of distinct chosen components is pure, $(D_1,\dots ,D_t)$ is a pure blockade.

The five vertices $v,a_1,b_1,b_2,a_2$ induce the cycle $v-a_1-b_1-b_2-a_2-v$. Indeed, [L1] supplies the four new edges and the edge $b_1{b}_2$ comes from the triangle. No other edge among these five vertices is present.

The remaining triangle vertex $b_3$ is adjacent to $b_1$ and $b_2$ but to neither $v,a_1,a_2$ in the chosen five-vertex set. Thus adjoining $b_3$ to the cycle from step 1.1 yields a hat vertex adjacent to two adjacent cycle vertices.

Therefore the star-expansion of $K_3$ contains an induced hatted five-cycle.

The cited primary-source theorem constructs connected comb components of width at least $\gamma \mathrm{\mid }V(G)\mathrm{\mid }\mathrm{/}{t}^3$, proves their pattern triangle-free, and extracts a stable pattern set of size at least $t^{1\mathrm{/}2}\mathrm{/}2$.

The source chooses the critical exponent so those exact length and width bounds contradict criticality, thereby proving the stated Erdős-Hajnal property.