Comb Structure in co-Bird-Free Graphs

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.

Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs supplies the following definition: Let $G$ be a finite simple graph and let $A,B\subseteq V(G)$ be disjoint. An edge between $A$ and $B$ is an edge $ab$ with $a\in A$ and $b\in B$. The pair $(A,B)$ is: - complete when every $a\in A$ is adjacent to every $b\in B$; - anticomplete when no $a\in A$ is adjacent to any $b\in B$; - pure when it is complete or anticomplete; and - mixed when it is neither complete nor anticomplete. Adjacency is the symmetric edge relation of $G$ (def-finite-simple-graph, def-graph-adjacency-incidence-neighbourhood-and-degree). If $A=\mathrm{\varnothing }$ or $B=\mathrm{\varnothing }$, the pair is both complete and anticomplete, hence pure and not mixed.

$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 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.

Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs supplies the following definition: Let $G$ be a finite simple graph and let $A,B\subseteq V(G)$ be disjoint. An edge between $A$ and $B$ is an edge $ab$ with $a\in A$ and $b\in B$. The pair $(A,B)$ is: - complete when every $a\in A$ is adjacent to every $b\in B$; - anticomplete when no $a\in A$ is adjacent to any $b\in B$; - pure when it is complete or anticomplete; and - mixed when it is neither complete nor anticomplete. Adjacency is the symmetric edge relation of $G$ (def-finite-simple-graph, def-graph-adjacency-incidence-neighbourhood-and-degree). If $A=\mathrm{\varnothing }$ or $B=\mathrm{\varnothing }$, the pair is both complete and anticomplete, hence pure and not mixed.

$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 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.

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 mixed vertex on E is pure on both terminal edges 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$. If $u$ is mixed on $S$, it is nevertheless pure to both terminal edges $\{p_1,p_2\}$ and $\{p_4,p_5\}$.

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.

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.

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.

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.

Anticonnected graphs and anticonnected components supplies the following definition: A graph $G$ is anticonnected, or co-connected, when its complement $\bar{G}$ is connected (def-connected-graph-and-connected-component, def-graph-isomorphism-and-complement). An anticonnected component, or anticomponent, of $G$ is a vertex set $A\subseteq V(G)$ that is the vertex set of a connected component of $\bar{G}$. Equivalently, $G[A]$ is anticonnected and $A$ is inclusion-maximal with that property (def-subgraph-induced-subgraph-and-spanning-subgraph). Under the library convention, the null graph is not anticonnected, while a one-vertex graph is anticonnected.

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.

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.

Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs supplies the following definition: Let $G$ be a finite simple graph and let $A,B\subseteq V(G)$ be disjoint. An edge between $A$ and $B$ is an edge $ab$ with $a\in A$ and $b\in B$. The pair $(A,B)$ is: - complete when every $a\in A$ is adjacent to every $b\in B$; - anticomplete when no $a\in A$ is adjacent to any $b\in B$; - pure when it is complete or anticomplete; and - mixed when it is neither complete nor anticomplete. Adjacency is the symmetric edge relation of $G$ (def-finite-simple-graph, def-graph-adjacency-incidence-neighbourhood-and-degree). If $A=\mathrm{\varnothing }$ or $B=\mathrm{\varnothing }$, the pair is both complete and anticomplete, hence pure and not mixed.

The E overlap blockade and mixed quotient sequence supplies the following definition: Fix a comb block $B_i$ with nonempty $E$ overlap support $X_i$. By lem-e-overlap-classes-form-an-anticonnected-partition, its overlap classes are nonempty anticonnected sets partitioning $X_i$. Fix an enumeration of the finite set $B_i$, and order the classes by their least enumerated vertex to obtain ${\mathcal{L}}^1$. Define recursively ${\mathcal{L}}^{s+1}={\mathcal{L}}^s\mathrm{/}\mathcal{M}$ for $s\ge 1$, using def-quotient-blockade-by-mixed-block-reachability and its least-member ordering. Thus one replaces each mixed-reachability class of blocks by its union. This construction is used only when $X_i\mathrm{\ne }\mathrm{\varnothing }$.

A quotient block of connected or anticonnected blocks is again connected or anticonnected supplies the following statement: Let $\mathcal{L}$ be a blockade and let $D$ be a block of the quotient blockade $\mathcal{L}\mathrm{/}\mathcal{M}$. 1. If every block of $\mathcal{L}$ contained in $D$ induces a connected subgraph, then $G[D]$ is connected. 2. If every block of $\mathcal{L}$ contained in $D$ induces an anticonnected subgraph, then $G[D]$ is anticonnected.

The well-ordering principle supplies the following statement: Every nonempty subset $S\subseteq \mathbb{N}$ has a least element: there is $\mathrm{\ell }\in S$ with $\mathrm{\ell }\le s$ for all $s\in S$.

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$.

A vertex mixed on an anticonnected set yields opposite adjacency on a nonedge supplies the following statement: Let $G$ be a finite graph, let $A\subseteq V(G)$ be anticonnected, and let $v\in V(G)\setminus A$ be mixed on $A$. Then there exist distinct vertices $b,b^{\mathrm{\prime }}\in A$ such that $b{b}^{\mathrm{\prime }}\mathrm{\notin }E(G),vb\in E(G),v{b}^{\mathrm{\prime }}\mathrm{\notin }E(G)\mathrm{.}$

Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs supplies the following definition: Let $G$ be a finite simple graph and let $A,B\subseteq V(G)$ be disjoint. An edge between $A$ and $B$ is an edge $ab$ with $a\in A$ and $b\in B$. The pair $(A,B)$ is: - complete when every $a\in A$ is adjacent to every $b\in B$; - anticomplete when no $a\in A$ is adjacent to any $b\in B$; - pure when it is complete or anticomplete; and - mixed when it is neither complete nor anticomplete. Adjacency is the symmetric edge relation of $G$ (def-finite-simple-graph, def-graph-adjacency-incidence-neighbourhood-and-degree). If $A=\mathrm{\varnothing }$ or $B=\mathrm{\varnothing }$, the pair is both complete and anticomplete, hence pure and not mixed.

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$.

Purity propagates through E overlap chains supplies the following statement: Fix a comb block $B_i$ and an $E$ overlap class $A$. If $u\mathrm{\notin }A$ is pure to every induced $E$ contained in $A$, then $u$ is pure to $A$. In particular, any $u\mathrm{\notin }{B}_i$ pure to every induced $E$ in $B_i$ is pure to every overlap class.

The E overlap blockade and mixed quotient sequence supplies the following definition: Fix a comb block $B_i$ with nonempty $E$ overlap support $X_i$. By lem-e-overlap-classes-form-an-anticonnected-partition, its overlap classes are nonempty anticonnected sets partitioning $X_i$. Fix an enumeration of the finite set $B_i$, and order the classes by their least enumerated vertex to obtain ${\mathcal{L}}^1$. Define recursively ${\mathcal{L}}^{s+1}={\mathcal{L}}^s\mathrm{/}\mathcal{M}$ for $s\ge 1$, using def-quotient-blockade-by-mixed-block-reachability and its least-member ordering. Thus one replaces each mixed-reachability class of blocks by its union. This construction is used only when $X_i\mathrm{\ne }\mathrm{\varnothing }$.

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.

A separated anticonnected block pair forbids mixing in one direction supplies the following statement: Let $G$ be finite simple and co-Bird-free. Let $D_1,D_2$ be disjoint nonempty vertex sets, with $D_2$ anticonnected. Suppose distinct $x,y,z\mathrm{\notin }{D}_1\cup D_2$ satisfy $xy\mathrm{\notin }E(G)$, both $x,y$ are complete to $D_1\cup D_2$, $zx\in E(G)$, $zy\mathrm{\notin }E(G)$, and $z$ is complete to $D_1$ and anticomplete to $D_2$. Then no vertex of $D_1$ is mixed on $D_2$.

A vertex mixed on a quotient block but pure on each member block yields two mixed member blocks with opposite adjacency supplies the following statement: Let $D$ be a block of the quotient blockade $\mathcal{L}\mathrm{/}\mathcal{M}$, and let $u\mathrm{\notin }D$ be a vertex. Suppose that $u$ is mixed on $D$ but is pure to every original block of $\mathcal{L}$ contained in $D$. Then there are two original blocks $A_1,A_2$ of $\mathcal{L}$, both contained in $D$, such that 1. $A_1$ and $A_2$ are mixed; and 2. $u$ is complete to $A_1$ and anticomplete to $A_2$.

A quotient-level mixed-block witness descends to two mixed member blocks supplies the following statement: Let $\mathcal{L}$ be a blockade in a graph $G$, and suppose that every block of $\mathcal{L}$ is connected or every block is anticonnected. Let $D_1,D_2$ be distinct mixed blocks of the quotient blockade $\mathcal{L}\mathrm{/}\mathcal{M}$. Assume there are vertices $x,y,u\mathrm{\notin }{D}_1\cup D_2$ such that: 1. $x$ and $y$ are nonadjacent and both are complete to $D_1\cup D_2$; 2. $u\in N(x)\setminus N(y)$, with $u$ complete to $D_1$ and anticomplete to $D_2$; and 3. no vertex of $D_1$ is mixed on $D_2$. Then there are mixed original blocks $A_1,A_2$ of $\mathcal{L}$, both contained in $D_1$, and vertices $x^{\mathrm{\prime }},y^{\mathrm{\prime }},u^{\mathrm{\prime }}\mathrm{\notin }{A}_1\cup A_2$ such that: 1. $x^{\mathrm{\prime }}$ and $y^{\mathrm{\prime }}$ are nonadjacent and both are complete to $A_1\cup A_2$; and 2. $u^{\mathrm{\prime }}\in N(x^{\mathrm{\prime }})\setminus N(y^{\mathrm{\prime }})$, with $u^{\mathrm{\prime }}$ complete to $A_1$ and anticomplete to $A_2$.

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.

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.

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. Throughout this definition, “the graph in def-e-graph-and-co-e-graph” means the $E$-graph defined there, not the co-$E$ graph.