Comb Structure in co-Bird-Free Graphs — Examples

The edge-plus-isolate co-Bird obstruction supplies the following statement: Let $G$ be a finite simple co-Bird-free graph. Let $x,y,u$ be distinct vertices outside the indicated induced subgraph, with $xy\mathrm{\notin }E(G)$, $ux\in E(G)$ and $uy\mathrm{\notin }E(G)$, and with $x,y$ complete to that subgraph. If $H=\{a,b,c\}$ induces just the edge $ab$, then $u$ cannot be mixed on $\{a,b\}$ and nonadjacent to $c$.

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.

The path-plus-isolate co-Bird obstruction supplies the following statement: Let $G$ be a finite simple co-Bird-free graph. Let $x,y,u$ be distinct vertices outside the indicated induced subgraph, with $xy\mathrm{\notin }E(G)$, $ux\in E(G)$ and $uy\mathrm{\notin }E(G)$, and with $x,y$ complete to that subgraph. If $H=\{a,b,c,d\}$ induces the path $a-b-c$ and isolated vertex $d$, then $u$ cannot be adjacent to $d$ and two consecutive vertices of the path and nonadjacent to the remaining endpoint.

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.

The edge-plus-isolate co-Bird obstruction supplies the following statement: Let $G$ be a finite simple co-Bird-free graph. Let $x,y,u$ be distinct vertices outside the indicated induced subgraph, with $xy\mathrm{\notin }E(G)$, $ux\in E(G)$ and $uy\mathrm{\notin }E(G)$, and with $x,y$ complete to that subgraph. If $H=\{a,b,c\}$ induces just the edge $ab$, then $u$ cannot be mixed on $\{a,b\}$ and nonadjacent to $c$.

The path-plus-isolate co-Bird obstruction supplies the following statement: Let $G$ be a finite simple co-Bird-free graph. Let $x,y,u$ be distinct vertices outside the indicated induced subgraph, with $xy\mathrm{\notin }E(G)$, $ux\in E(G)$ and $uy\mathrm{\notin }E(G)$, and with $x,y$ complete to that subgraph. If $H=\{a,b,c,d\}$ induces the path $a-b-c$ and isolated vertex $d$, then $u$ cannot be adjacent to $d$ and two consecutive vertices of the path and nonadjacent to the remaining endpoint.

Complete nonedge pairs force purity on induced E graphs supplies the following statement: Let $G$ be a finite simple co-Bird-free graph. Let $x,y,u$ be distinct vertices outside the indicated induced subgraph, with $xy\mathrm{\notin }E(G)$, $ux\in E(G)$ and $uy\mathrm{\notin }E(G)$, and with $x,y$ complete to that subgraph. Let $S=\{p_1,p_2,p_3,p_4,p_5,q\}$ induce $E$, with edges exactly $p_1{p}_2,p_2{p}_3,p_3{p}_4,p_4{p}_5,p_{3}q$. Then $u$ is pure to $S$. In particular, in an $(\mathrm{\ell },w)$-comb with an outside vertex $v$ complete to all blocks and anticomplete to all teeth, each $u\in B_k$, $k\mathrm{\ne }i$, is pure to every induced $E$ in $B_i$.

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.

A special-vertex co-Bird-free comb admits an E-free structural partition 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. For every $i\in [\mathrm{\ell }]$ there exist 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 satisfying: the sequence is a pure blockade, its pattern is $E$-free, and each individual vertex of every other comb block is pure to each $A_j^i$. The blocks $A_j^i$ may additionally be chosen anticonnected.

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.

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.