A special-vertex co-Bird-free comb admits an E-free structural partition

E overlap chains inside one comb block supplies the following definition: Fix a block $B_i$ of a finite graph comb (def-comb-in-a-graph). Let ${\mathcal{E}}_i$ consist of all six-vertex subsets of $B_i$ inducing the graph in def-e-graph-and-co-e-graph. Put $X_i={\bigcup }_{S\in {\mathcal{E}}_i}S$ and $Y_i=B_i\setminus X_i$. For $d,e\in X_i$, define $d<msub><mi>R</mi><mi>i</mi></msub>e$ if there exist $m\ge 0$ and vertices $d=d_0,d_1,\dots ,d_m=e$ in $X_i$ such that each consecutive pair is contained in some $S\in {\mathcal{E}}_i$. A zero-length chain is allowed. If ${\mathcal{E}}_i$ is empty then $X_i$ and the relation are empty. We call this the $E$ overlap chain relation.

E overlap quotients terminate at a pure blockade supplies the following statement: For nonempty overlap support, put $n=\mathrm{\mid }{\mathcal{L}}^1\mathrm{\mid }$. Every stage ${\mathcal{L}}^s$ partitions the same support into nonempty anticonnected blocks and coarsens ${\mathcal{L}}^1$. There is a least $q\ge 1$ for which ${\mathcal{L}}^q$ is pure, with $q\le n$. At most $n-1$ strict transitions occur, and all stages from $q$ onward are identical.

The terminal E overlap pattern is E-free supplies the following statement: For a comb block with nonempty $E$ overlap support, the pattern graph of its terminal pure quotient blockade ${\mathcal{L}}^q$ is $E$-free.

External purity survives every E overlap quotient supplies the following statement: 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. Fix $i$ with nonempty $E$ overlap support. For every $s\ge 1$, every block $L$ of ${\mathcal{L}}^s$ and every vertex $u\in {\bigcup }_{k\mathrm{\ne }i}{B}_k$, the vertex $u$ is pure to $L$.

Combs in a graph supplies the following definition: Let $\mathrm{\ell }\in \mathbb{N}$ with $\mathrm{\ell }\ge 1$, and let $w>0$. An $(\mathrm{\ell },w)$-comb in a graph $G$ is a sequence of pairs $((a_i,B_i):i\in [\mathrm{\ell }])$ satisfying the conditions below. Here a vertex $a$ is complete to (respectively, anticomplete to) a set $B$ when the pair $(\{a\},B)$ is complete (respectively, anticomplete) in the sense of def-edges-between-sets-and-pure-mixed-pairs. 1. $(B_1,\dots ,B_{\mathrm{\ell }})$ is an $(\mathrm{\ell },w)$-blockade; 2. the vertices $a_1,\dots ,a_{\mathrm{\ell }}$ are distinct; 3. the set $\{a_1,\dots ,a_{\mathrm{\ell }}\}$ is disjoint from every block $B_i$; and 4. for every $i\in [\mathrm{\ell }]$, the vertex $a_i$ is complete to $B_i$; and 5. for all distinct $i,j\in [\mathrm{\ell }]$, the vertex $a_i$ is anticomplete to $B_j$. The vertices $a_i$ are the teeth of the comb.

$H$-free and $\mathcal{F}$-free graphs under the induced-subgraph convention supplies the following definition: For finite graphs $H$ and $G$, the graph $G$ is $H$-free when $G$ has no induced copy of $H$ (def-induced-embedding-and-induced-copy). Equivalently, ${\mathrm{ind}}_H(G)=0$ (def-induced-copy-number). For a family $\mathcal{F}$ of finite graphs, a finite graph $G$ is $\mathcal{F}$-free when it is $H$-free for every $H\in \mathcal{F}$. Throughout this page, “free” always refers to induced subgraphs. It does not merely prohibit ordinary subgraph copies.

The $E$-graph and co-$E$ supplies the following definition: The $E$-graph is the graph on vertices $\{p_1,p_2,p_3,p_4,p_5,q\}$ with edge set $\{p_1{p}_2,p_2{p}_3,p_3{p}_4,p_4{p}_5,p_{3}q\}\mathrm{.}$ Thus $p_1{p}_2{p}_3{p}_4{p}_5$ is a five-vertex path and $q$ is a leaf attached to its middle vertex $p_3$. The co-$E$ graph is the complement of this graph.

The Bird graph and co-Bird supplies the following definition: The Bird graph is the graph on vertices $\{x_1,x_2,x_3,y,z,w\}$ with edge set $\{x_1{x}_2,x_2{x}_3,x_1{x}_3,x_{1}y,x_{2}z,yw\}\mathrm{.}$ So $\{x_1,x_2,x_3,y,z\}$ spans the bull, and $w$ is a new leaf attached to the horn vertex $y$. The co-Bird graph is the complement of the Bird graph.