Comb Structure in co-E-Free Graphs — Examples

In the first configuration the nonedges are exactly $xy,yu,uc,ca,ub$, the $E$-edges in the order $(p_1,p_2,p_3,p_4,p_5,q)=(x,y,u,c,a,b)$. In the second they are exactly $ca,ad,du,uy,db$, the $E$-edges in the order $(p_1,p_2,p_3,p_4,p_5,q)=(c,a,d,u,y,b)$. Hence both graphs are co-$E$.

Their displayed paths are induced and the mixed vertex has respectively two consecutive nonneighbours and three consecutive neighbours.

This verifies both finite witnesses.

Every vertex of $B_i$ belongs to one of the two induced copies, so $X_i=B_i$. For any $d,d^{\mathrm{\prime }}\in B_i$, the vertex sequence $d,v_1,d^{\mathrm{\prime }}$ has each consecutive pair in one of those copies; omit repeated consecutive vertices if necessary. Thus [F1] gives $d{\sim }_{H_5}{d}^{\mathrm{\prime }}$, and $B_i$ is the unique overlap class.

The initial overlap blockade is therefore $(B_i)$. There is no pair of distinct blocks, so it is pure vacuously. Its mixed-block reachability relation has just the singleton class $\{B_i\}$; replacing that class by its union returns $(B_i)$. Every iterate is consequently $(B_i)$, already terminal at the first stage.

This gives the claimed overlap class and terminal quotient.

The graph is bipartite, with sides ${\bigcup }_i{B}_i$ and $\{a_1,\dots ,a_4,v\}$. By [F1] it is co-$E$-free.

Choose $x_i\in B_i$, set $X_i=\{x_i\}$ and $Y_i=B_i\setminus \{x_i\}$. Each $Y_i$ is independent and co-$E$-free.

Each singleton $X_i$ has a pure one-block blockade and one-vertex pattern, and every vertex in another block is anticomplete to it. Thus the structural clauses hold.