Comb Structure in co-E-Free Graphs

The class of $\{H_0,\mathrm{c}\mathrm{o}\text{-}E\}$-free graphs is a hereditary subclass of the class of $H_0$-free graphs, and the class of $\{H_i,\overline{P_5}\}$-free graphs is a hereditary subclass of the class of $\overline{P_5}$-free graphs. Thus [F1]--[F3] give the Erdős–Hajnal property for both families, for every $i\in [5]$.

Fix $i\in [5]$ and suppose that $\{H_{i-1},\mathrm{c}\mathrm{o}\text{-}E\}$ has the property. In $\mathcal{F}=\{H_i,\mathrm{c}\mathrm{o}\text{-}E\}$, deleting the leaf $v_i^{\mathrm{\prime }}$ of $H_i$ gives $H_{i-1}$. The vertex $q$ is a leaf of $E$, so it is a co-leaf of co-$E$, and deleting it from co-$E$ leaves $\overline{P_5}$. Hence the two modified families in [F4] are exactly $\{H_{i-1},\mathrm{c}\mathrm{o}\text{-}E\}$ and $\{H_i,\overline{P_5}\}$.

Step 1.2, the induction hypothesis, and the second base family from step 1.1 let [F4] yield the property for $\{H_i,\mathrm{c}\mathrm{o}\text{-}E\}$.

Starting with $i=1$ and repeating step 2.1 through $i=5$ proves the property for $\{H_5,\mathrm{c}\mathrm{o}\text{-}E\}$.

Set $c_1=c_3=c\mathrm{/}4>0$ and $c_2=10\mathrm{/}c>0$. Fix an arbitrary $\bar{\mathcal{H}}$-free finite graph $G$ and a special-vertex $(\mathrm{\ell },w)$-comb from Property (*) for a finite graph family, with integral $\mathrm{\ell }\ge 4$ and real $w\ge 4$. Use its supplied local partition. Suppose that all three property-$(\ast )$ outcomes with these constants fail.

If $\mathrm{\mid }{Y}_i\mathrm{\mid }\ge w\mathrm{/}2$ for some $i$, then $Y_i$ is nonempty and [F1] supplies a clique or stable set of size at least $(w\mathrm{/}2{)}^c\ge w^{c\mathrm{/}2}\ge w^{c\mathrm{/}4}$, since $w\ge 4$. This contradicts the first failure. Hence every $\mathrm{\mid }{Y}_i\mathrm{\mid }<w\mathrm{/}2$, and $\mathrm{\mid }{B}_i\mathrm{\mid }\ge w$ implies $\mathrm{\mid }{X}_i\mathrm{\mid }>w\mathrm{/}2$.

If every partition has a block $D_i=A_{j_i}^i$ of size at least $w\mathrm{/}(2\mathrm{\ell })$, choose one for each of the finitely many indices $i$. Fix distinct $i,h$. Each vertex of $D_h$ is complete or anticomplete to $D_i$ by the local external-purity clause. Two vertices of $D_h$ with opposite relations would make any vertex of the nonempty $D_i$ mixed on $D_h$, contrary to the same clause with $i,h$ reversed. Thus $D_i,D_h$ are pure. The disjoint sequence $(D_1,\dots ,D_{\mathrm{\ell }})$ is consequently a pure blockade of width at least $w\mathrm{/}(2\mathrm{\ell })\ge w\mathrm{/}{\mathrm{\ell }}^2$, contradicting the third failure.

By step 2.2 there is an index $i$ such that every $\mathrm{\mid }{A}_j^i\mathrm{\mid }<w\mathrm{/}(2\mathrm{\ell })$, hence is at most this bound. Put $X=X_i$, $t=t_i$, and reorder these blocks as $A_1,\dots ,A_t$ in nonincreasing size. Reordering preserves purity and changes the pattern only by relabelling. Since $w\mathrm{/}2<\mathrm{\mid }X\mathrm{\mid }={\sum }_{j=1}^t\mathrm{\mid }{A}_j\mathrm{\mid }\le tw\mathrm{/}(2\mathrm{\ell })$, we have $t\ge \mathrm{\ell }$. The reordered pattern is still ${\mathcal{F}}_2$-free.

Form the cutoffs of [F3]. They reach $t$: for example, ${\mathrm{\ell }}^{t\mathrm{/}2}\ge 2^t\ge t$ for the positive integer $t$, the latter elementary inequality following by induction. Let $q$ be the first index with $m_q=t$. Since $m_1\le \sqrt{\mathrm{\ell }}<\mathrm{\ell }\le t$, we have $q\ge 2$. For $2\le r\le q$, the integer $m_{r-1}+1$ is at most $t$ and at most $2{\mathrm{\ell }}^{(r-1)\mathrm{/}2}\le {\mathrm{\ell }}^{r\mathrm{/}2}$, so $m_r\ge m_{r-1}+1$. Thus all layers $C_1,\dots ,C_q$ are nonempty and partition the blocks in order.

For $1\le r<q$, put $x={\mathrm{\ell }}^{r\mathrm{/}2}\ge 2$. Then $m_r=\lfloor x\rfloor \ge 2$, so $x<m_r+1\le m_r^2$, yielding $m_r\ge \sqrt{x}={\mathrm{\ell }}^{r\mathrm{/}4}$. Also $m_1\le {\mathrm{\ell }}^{1\mathrm{/}2}$ and each $C_{r+1}$ contains at most $m_{r+1}\le {\mathrm{\ell }}^{(r+1)\mathrm{/}2}$ blocks, including when $r+1=q$.

Suppose a preterminal layer $C_r$, $1\le r<q$, has every block of size at least $w\mathrm{/}{\mathrm{\ell }}^{5r\mathrm{/}2}$. The first $m_r$ blocks all have at least that size by their nonincreasing order. Their induced pattern is nonempty and ${\mathcal{F}}_2$-free, so [F1] gives a pattern clique or stable set $S$ of integral cardinality $k\ge m_r^c\ge {\mathrm{\ell }}^{cr\mathrm{/}4}$. By [F2], the blocks indexed by $S$ form a complete or anticomplete blockade of length $k$ and width at least $w\mathrm{/}{\mathrm{\ell }}^{5r\mathrm{/}2}$.

Since $k^{10\mathrm{/}c}\ge {\mathrm{\ell }}^{5r\mathrm{/}2}$ and $k\ge {\mathrm{\ell }}^{cr\mathrm{/}4}\ge {\mathrm{\ell }}^{c\mathrm{/}4}$, this blockade has width at least $w\mathrm{/}{k}^{10\mathrm{/}c}$ and satisfies the second property-$(\ast )$ outcome. That contradicts step 1.1. Therefore every preterminal $C_r$ contains a block of size strictly less than $w\mathrm{/}{\mathrm{\ell }}^{5r\mathrm{/}2}$.

The first layer contributes at most ${\mathrm{\ell }}^{1\mathrm{/}2}w\mathrm{/}(2\mathrm{\ell })=w\mathrm{/}(2\sqrt{\mathrm{\ell }})\le w\mathrm{/}4$ vertices. For $1\le r<q$, every block in $C_{r+1}$ follows the small block in $C_r$ and has size less than $w\mathrm{/}{\mathrm{\ell }}^{5r\mathrm{/}2}$. Hence $C_{r+1}$ contributes less than $w{\mathrm{\ell }}^{(r+1)\mathrm{/}2-5r\mathrm{/}2}=w{\mathrm{\ell }}^{1\mathrm{/}2-2r}$.

Because $\mathrm{\ell }\ge 4$ and $1\mathrm{/}2-2r<0$, the sum of the latter bounds is at most $w{\sum }_{r\ge 1}{4}^{1\mathrm{/}2-2r}=(w\mathrm{/}8){\sum }_{s\ge 0}{16}^{-s}=2w\mathrm{/}15$. All layers have been counted, so $\mathrm{\mid }X\mathrm{\mid }<w\mathrm{/}4+2w\mathrm{/}15=23w\mathrm{/}60<w\mathrm{/}2$, contradicting step 2.1.

Thus one of the three outcomes holds for every special-vertex comb required by Property (*) for a finite graph family, with constants independent of $G$ and the comb. This proves that $\mathcal{H}$ has property $(\ast )$.

Suppose two consecutive vertices of $P$ are nonneighbours of $u$. Travelling from a neighbour of $u$ on $P$ to the first such consecutive pair and taking the first change gives an induced subpath $a-b-c$ with $ua$ an edge and $ub,uc$ nonedges.

If instead $u$ has three consecutive neighbours, reverse $P$ if needed and take the last such run before an adjacency change. There is an induced subpath $a-b-c-d$ with $ua,ub,uc$ edges and $ud$ a nonedge.

On $\{x,y,u,a,b,c\}$ the nonedges are exactly the $E$-edges under $(p_1,p_2,p_3,p_4,p_5,q)=(x,y,u,c,a,b)$: they are $xy,yu,uc,ca,ub$. Thus this induced subgraph is co-$E$, contrary to [F1].

On $\{y,u,a,b,c,d\}$ the nonedges are exactly the $E$-edges under $(p_1,p_2,p_3,p_4,p_5,q)=(c,a,d,u,y,b)$: they are $ca,ad,du,uy,db$. This is an induced co-$E$, again a contradiction.

Both assumed runs are impossible, proving the two assertions.

Suppose $u$ is mixed on the $H_5$. If $u$ is complete to the rim and some $u{v}_j^{\mathrm{\prime }}$ is a nonedge, then $u$ is mixed on the induced path $v_j^{\mathrm{\prime }}-v_j-v_{j+1}-v_{j+2}$ and has three consecutive neighbours there, contrary to [F2]. Thus $u$ is adjacent to every $v_j^{\mathrm{\prime }}$. If $uw$ failed, $\{v_1^{\mathrm{\prime }},u,v_1,v_2,v_3,w\}$ induces co-$E$; hence $uw$ holds and $u$ is complete to $H_5$, a contradiction.

If $u$ is anticomplete to the rim and some $u{v}_j^{\mathrm{\prime }}$ is an edge, then $u$ is mixed on $v_j^{\mathrm{\prime }}-v_j-v_{j+1}$ with two consecutive nonneighbours, contrary to [F2]. Thus every $u{v}_j^{\mathrm{\prime }}$ is a nonedge. If $uw$ were an edge, then $u$ would be mixed on $v_1^{\mathrm{\prime }}-v_1-w$ with two consecutive nonneighbours, again contrary to [F2]. Hence $uw$ is a nonedge, so $u$ is anticomplete to $H_5$, also a contradiction.

It remains that $u$ is mixed on the rim. Any cyclic run of two rim nonneighbours or three rim neighbours, together with a vertex of the opposite adjacency supplied by mixedness, lies in an induced rim subpath to which [F2] applies. Thus the two run restrictions force, up to cyclic relabeling, $N(u)\cap V(C)=\{v_1,v_3,v_4\}$. If $uw$ were a nonedge, then $u$ would be mixed on $v_4-w-v_2$ with two consecutive nonneighbours; if $u{v}_1^{\mathrm{\prime }}$ were a nonedge, then $u$ would be mixed on $v_1^{\mathrm{\prime }}-v_1-w-v_3$ with three consecutive neighbours. Hence [F2] gives $uw,u{v}_1^{\mathrm{\prime }}\in E(G)$; then $\{u,w,v_1^{\mathrm{\prime }},v_1,v_2,v_3\}$ induces co-$E$, impossible.

Every possible rim relation contradicts mixedness, so $u$ is pure to the induced $H_5$.

Let $r,s\in C$. By [F1], choose an overlap chain from a copy containing $r$ to a copy containing $s$. Within each copy, [F2] gives paths from its entering vertex to its shared vertex and then to its exiting vertex.

Concatenating these paths at the shared vertices is a walk in $G[C]$ from $r$ to $s$, and deleting repetitions gives a path. Thus every two vertices of $C$ are connected.

Hence $G[C]$ is connected.

Two consecutive copies in an overlap chain share a vertex. By [F2], $u$ cannot be complete to one and anticomplete to the other, since their shared vertex would then be both adjacent and nonadjacent to $u$.

Thus the complete/anticomplete label is constant along every overlap chain. By [F1], every vertex of $C$ lies in a copy reached from any fixed copy, so all vertices of $C$ receive one label.

Hence $u$ is complete or anticomplete to $C$, as claimed.

If ${\mathcal{L}}^s$ is not pure, two distinct blocks are mixed. They lie in one mixed-reachability class, so [F2] merges at least two blocks and strictly decreases the positive integer number of blocks.

Suppose no iterate were pure. Step 1.1 would give an infinite strictly decreasing sequence of positive integers, the successive numbers of blocks.

The set of values of that sequence has a least element by well-ordering, but its successor in the sequence is smaller, a contradiction. Therefore a first pure iterate exists.

Choose $a,b\in S$ with $ua$ an edge and $ub$ a nonedge by [F1], and choose an $a$--$b$ path in $G[S]$ by [F2].

Along this finite path, the adjacency indicator to $u$ begins at $1$ and ends at $0$, so it first changes across one consecutive pair. That pair is an edge of $G[S]$ with opposite adjacencies to $u$.

This is the required mixed edge.

Write ${\mathcal{L}}^r$ for iterate $r\ge 1$. For any external comb-block vertex $u$, the comb and special-vertex hypotheses give $u\in N(v)\setminus N(a_i)$, with $v,a_i$ nonadjacent and complete to $B_i$. Thus [F1] makes $u$ pure to every induced $H_5$ in $B_i$, and [F2] makes it pure to each block of ${\mathcal{L}}^1$.

All blocks of every ${\mathcal{L}}^r$ are connected: start with the initial classes and repeatedly apply connectedness preservation in [F6].

Fix $s\ge 2$ and assume the assertion for $s-1$. Suppose an external vertex $u$ is mixed on a block $L$ of ${\mathcal{L}}^s$. By the induction hypothesis, each member block of ${\mathcal{L}}^{s-1}$ inside $L$ is complete or anticomplete to $u$, and both labels occur. By [F7], a mixed chain inside $L$ joins blocks of opposite labels; at a change of label, consecutive mixed blocks $D_1,D_2$ have $u$ complete to $D_1$ and anticomplete to $D_2$.

Consider any mixed blocks $D_1,D_2$ at level $r\ge 1$ with an outside triple $x,y,z$ satisfying: $xy$ is a nonedge, $x,y$ are complete to $D_1\cup D_2$, and $z\in N(x)\setminus N(y)$ is complete to $D_1$ and anticomplete to $D_2$. No vertex $b\in D_1$ is mixed on $D_2$. Indeed, if one were, connectedness and [F4] give an edge $c{c}^{\mathrm{\prime }}$ in $D_2$ with $bc$ an edge and $b{c}^{\mathrm{\prime }}$ a nonedge. Then $b-c-c^{\mathrm{\prime }}$ is induced, $x,y$ are outside and complete to it, and $z$ is mixed on it with consecutive nonneighbours $c,c^{\mathrm{\prime }}$, contrary to [F5].

The pair in step 1.3 has the required triple $(x,y,z)=(v,a_i,u)$ at level $s-1$. Whenever its current level $r$ exceeds one, apply [F3] to ${\mathcal{L}}^{r-1}$: step 1.2 supplies connected member blocks and step 2.1 supplies the directional no-mixed-vertex hypothesis. The resulting mixed blocks at level $r-1$ have an outside triple with all the same adjacency conditions. Repeating this finite descent reaches mixed initial classes $A_1,A_2$ and an outside triple $x^{\mathrm{\prime }},y^{\mathrm{\prime }},u^{\mathrm{\prime }}$ with $x^{\mathrm{\prime }}{y}^{\mathrm{\prime }}$ a nonedge, $x^{\mathrm{\prime }},y^{\mathrm{\prime }}$ complete to $A_1\cup A_2$, and $u^{\mathrm{\prime }}\in N(x^{\mathrm{\prime }})\setminus N(y^{\mathrm{\prime }})$ complete to $A_1$ and anticomplete to $A_2$. If $s=2$, the initial pair already has these properties.

Apply step 2.1 to $A_1,A_2,x^{\mathrm{\prime }},y^{\mathrm{\prime }},u^{\mathrm{\prime }}$. Every vertex of $A_1$ is pure to $A_2$. Since the pair $(A_1,A_2)$ is mixed, some vertex $p\in A_1$ is complete to $A_2$ and some vertex $q\in A_1$ is anticomplete to $A_2$; otherwise all vertices have the same label and the pair is pure. Therefore any $u_2\in A_2$ is adjacent to $p$ and nonadjacent to $q$, and is mixed on $A_1$. Such a vertex exists because a blockade block is nonempty.

The vertices $y^{\mathrm{\prime }},u^{\mathrm{\prime }}$ are outside $A_1$, nonadjacent, and both complete to $A_1$. Also $u_2\in N(y^{\mathrm{\prime }})\setminus N(u^{\mathrm{\prime }})$. Apply [F1] with $(x,y,u)=(y^{\mathrm{\prime }},u^{\mathrm{\prime }},u_2)$ to every induced $H_5$ contained in $A_1$, then [F2] to the overlap class $A_1$. It follows that $u_2$ is pure to $A_1$, contradicting step 4.1. Thus no external vertex is mixed on any block at level $s$. Together with the base case this proves the assertion for every iterate.

Suppose the pattern contains an induced $H_5$, and choose one vertex from each of its eleven corresponding nonempty blocks. By [F1], the selected vertices induce $H_5$ in the ambient graph.

If the pattern contains an induced co-$E$, selecting one vertex from each of its six blocks and using [F1] similarly induces co-$E$ in the ambient graph, contradicting co-$E$-freeness.

The eleven selected vertices lie in distinct terminal blocks. But [F2] says the vertices of every induced $H_5$ must already lie in one initial overlap class and hence in one terminal block, a contradiction.

Neither forbidden induced graph occurs in the pattern.

Fix $i$. Let $X_i^0$ be the vertices of $B_i$ contained in an induced $H_5$, and put $Y_i=B_i\setminus X_i^0$. Then $Y_i$ is $H_5$-free by definition and co-$E$-free as an induced subgraph, hence it is $\{H_5,\mathrm{c}\mathrm{o}\text{-}E\}$-free.

Assume-case nonempty: if $X_i^0\mathrm{\ne }\mathrm{\varnothing }$, set $X_i=X_i^0$ and take its terminal overlap quotient as the partition. Its pure-blockade and pattern clauses are [F1], and its cross-block purity clause is [F2].

Assume-case empty: if $X_i^0=\mathrm{\varnothing }$, choose $x_i\in B_i$, set $X_i=\{x_i\}$ and $Y_i=B_i\setminus \{x_i\}$. The singleton blockade on $X_i$ is pure, its pattern has one vertex and is forbidden-family-free, and every outside vertex is pure to it; $Y_i$ is $H_5$-free because $B_i$ was.

The two cases produce the required partition for this arbitrary $i$, and therefore for every comb block.

For $\mathcal{H}=\{E\}$, its complement family is $\bar{\mathcal{H}}=\{\mathrm{c}\mathrm{o}\text{-}E\}$. Thus the given graph is in the setting of [F2].

Take ${\mathcal{F}}_1={\mathcal{F}}_2=\{H_5,\mathrm{c}\mathrm{o}\text{-}E\}$. Fact [F1] supplies their common Erdős–Hajnal constant, and [F2] supplies the local partition for every special-vertex comb in the graph of step 1.1.

Applying [F3] now proves that $\{E\}$ has property $(\ast )$.