# Apex Graphs and Cographs

Jagdeep Singh  Department of Mathematics and Statistics
Binghamton University
Binghamton, New York<EMAIL_ADDRESS>,  Vaidy Sivaraman  Department
of Mathematics and Statistics
Mississippi State University
Mississippi<EMAIL_ADDRESS>and  Thomas Zaslavsky  Department of
Mathematics and Statistics
Binghamton University
Binghamton, New York<EMAIL_ADDRESS>
###### Abstract.

A class $\mathcal{G}$ of graphs is called hereditary if it is closed under
taking induced subgraphs. We denote by $\mathcal{G}^{\mathrm{apex}}$ the class
of graphs $G$ that contain a vertex $v$ such that $G-v$ is in $\mathcal{G}$.
We prove that if a hereditary class $\mathcal{G}$ has finitely many forbidden
induced subgraphs, then so does $\mathcal{G}^{\mathrm{apex}}$.

The hereditary class of cographs consists of all graphs $G$ that can be
generated from $K_{1}$ using complementation and disjoint union. A graph is an
apex cograph if it contains a vertex whose deletion results in a cograph.
Cographs are precisely the graphs that do not have the $4$-vertex path as an
induced subgraph. Our main result finds all such forbidden induced subgraphs
for the class of apex cographs.

###### Key words and phrases:

Apex graph, Cograph, Forbidden induced subgraph.

###### 2010 Mathematics Subject Classification:

05C75

##  1\. Introduction

We consider finite, simple, and undirected graphs. An induced subgraph of a
graph $G$ is a graph $H$ that can be obtained from $G$ by a sequence of vertex
deletions; we write $G[T]$ for the subgraph if $T$ is the set of remaining
vertices. We say that $G$ contains $H$ when $H$ is an induced subgraph of $G$.
A class $\mathcal{G}$ of graphs is called hereditary if it is closed under
taking induced subgraphs.

A cograph is a graph that can be generated from the single-vertex graph
$K_{1}$ using the operations of complementation and disjoint union. The class
of cographs has been extensively studied over the last fifty years (see, for
example, [2, jung, 5]). Due to the following characterization, cographs are
also called $P_{4}$-free graphs [1].

######  Theorem 1.1.

A graph $G$ is a cograph if and only if $G$ does not contain the path $P_{4}$
on four vertices as an induced subgraph.

The apex class, $\mathcal{G}^{\mathrm{apex}}$, for a class $\mathcal{G}$ is
the class of graphs $G$ that contain a vertex $v$ such that $G-v$ is in
$\mathcal{G}$. A graph $G$ is an apex cograph if it has a vertex $v$ such that
$G-v$ is a cograph. In Theorem 1.3 we characterize apex cographs in the spirit
of Theorem 1.1.

For a hereditary class $\mathcal{G}$, we call a graph $H$ a forbidden induced
subgraph for $\mathcal{G}$ if $H$ is not in $\mathcal{G}$ but every proper
induced subgraph of $H$ is in $\mathcal{G}$. Thus, a graph $G$ is in
$\mathcal{G}$ if and only if $G$ contains no forbidden induced subgraph for
$\mathcal{G}$. It is easy to see that the class of cographs is hereditary; by
Theorem 1.1 it has only one forbidden induced subgraph. We prove that the
class of apex cographs also has a finite number of forbidden induced
subgraphs. Indeed, we show that in general, if a hereditary class
$\mathcal{G}$ has a finite number of forbidden induced subgraphs, then so does
$\mathcal{G}^{\mathrm{apex}}$. The precise statement is the following theorem.

######  Theorem 1.2.

Let $\mathcal{G}$ be a hereditary class of graphs and let $c$ denote the
maximum number of vertices in a forbidden induced subgraph for $\mathcal{G}$.
Then every forbidden induced subgraph for $\mathcal{G}^{\mathrm{apex}}$ has at
most $\lfloor{\frac{1}{4}(c+2)^{2}}\rfloor$ vertices.

Its proof is in Section 2. As a consequence of Theorem 1.2, the number of
vertices of a forbidden induced subgraph for the class of apex cographs is at
most nine. In Section 3, we show that there are none with nine vertices and we
list all of the forbidden induced subgraphs.

######  Theorem 1.3.

Let $G$ be a forbidden induced subgraph for the class of apex cographs. Then
$5\leq|V(G)|\leq 8$, and $G$ or its complement $\overline{G}$ is isomorphic to
$C_{5}$ or one of the graphs in Figures 1, 2, and 3.

##  2\. Apex Exclusions

The main part of the proof of Theorem 1.2 is the following reduction lemma.

######  Proposition 2.1.

Let $\mathcal{G}$ be a hereditary class of graphs and let $c$ denote the
maximum number of vertices in a forbidden induced subgraph for $\mathcal{G}$.
If $G$ is a forbidden induced subgraph for $\mathcal{G}^{\mathrm{apex}}$, then
there are distinct subsets $S$ and $T$ of $V(G)$ such that $G[S]$ and $G[T]$
induce a forbidden induced subgraph for $\mathcal{G}$. Moreover, if $|S\cap
T|=k$ is minimal, then $|V(G)|\leq(c-k)(k+2)$.

###### Proof.

There is no vertex $v$ of $G$ such that $G-v$ is in $\mathcal{G}$, so $V(G)$
has distinct subsets $S$ and $T$ such that $G[S]$ induces a forbidden induced
subgraph for $\mathcal{G}$, and $G[T]$ induces a forbidden induced subgraph
for $\mathcal{G}$.

First we consider the possibility that $S\cap T$ is empty. If it were empty,
there would be no vertex in $V(G)-(S\cup T)$, because if there were such a
vertex $v$, then $G-v$ would be a proper induced subgraph of $G$ but not in
$\mathcal{G}^{\mathrm{apex}}$, a contradiction. It follows that $V(G)=S\cup
T$, so $|V(G)|\leq 2c$, verifying the proposition. Therefore, we may assume
$S\cap T$ is nonempty for every choice of $S$ and $T$.

We pick $S$ and $T$ such that $|S\cap T|$ is minimal and let $S\cap
T=\\{v_{1},\ldots,v_{k}\\}$. Since for each $1\leq i\leq k$, the graph
$G-v_{i}$ is not in $\mathcal{G}$, we have a subset $F_{i}$ of $V(G)-v_{i}$
such that $G[F_{i}]$ induces a forbidden induced subgraph for $\mathcal{G}$.
Observe that, if there is a vertex $x$ in $V(G)-(S\cup
T\cup\bigcup_{i=1}^{k}F_{i})$, then $G-x$ is not in
$\mathcal{G}^{\mathrm{apex}}$, a contradiction. Therefore, $V(G)=S\cup
T\cup\bigcup_{i=1}^{k}F_{i}$.

Next we show that for every $1\leq i\leq k$, we have $|F_{i}\cap(S\cup T)|\geq
k+1$. By our choice of $S$ and $T$, we have $|F_{i}\cap S|\geq k$ and
$|F_{i}\cap T|\geq k$. Since $F_{i}$ does not contain $v_{i}$, it follows that
$F_{i}$ intersects both $S-T$ and $T-S$. Therefore $|F_{i}\cap(S\cup T)|\geq
k+1$. Since $V(G)=S\cup T\cup\bigcup_{i=1}^{k}F_{i}$, we have $|V(G)|\leq
c+(c-k)+k(c-(k+1))=(c-k)(k+2)$. ∎

###### Proof of Theorem 1.2.

By Proposition 2.1, we have $|V(G)|\leq(c-k)(k+2)$ where $0\leq k\leq c$. The
upper bound attains its maximum value when $k=\frac{c-2}{2}$. Therefore,
$|V(G)|\leq\frac{1}{4}(c+2)^{2}$. ∎

##  3\. Apex Cograph Exclusions

The first lemma observes that the forbidden induced subgraphs for apex
cographs are closed under complementation. We omit its straightforward proof.

######  Lemma 3.1.

If $G$ is a forbidden induced subgraph for the class of apex cographs, then so
is its complement, $\overline{G}$.

As $G$ or its complement is connected, by Lemma 3.1 we need to consider only
connected graphs to find all forbidden induced subgraphs for apex cographs up
to complementation. Such forbidden graphs have at least five vertices, because
any graph with fewer vertices is an apex cograph. We implemented the following
algorithm on connected graphs using SageMath [4]; in Figures 1–3 we list all
such forbidden induced subgraphs up to complementation. The graphs were drawn
using SageMath.

Algorithm Finding forbidden induced subgraphs for apex cographs up to
complementation

0: $n=5,6,7,8,$ or $9$.

Set PreList $\leftarrow\emptyset$, FinalList $\leftarrow\emptyset$,
$i\leftarrow 0$

Generate all connected graphs of order $n$ using nauty geng [3] and store in
an iterator $L$

for $g$ in $L$ such that $g$ is not a cograph do

for $v$ in $V(g)$ do

$h=g-v$

if $h$ is not a cograph and $h-w$ is a cograph for some $w$ in $V(h)$ then

$i\leftarrow i+1$

if $i$ equals $|V(g)|$ then

Add $g$ to PreList

for $g$ in PreList do

if FinalList does not contain $\overline{g}$ then

add $g$ to FinalList

The results were the following:

Graphs on five vertices. The $5$-vertex cycle $C_{5}$ is the unique $5$-vertex
forbidden induced subgraph for apex cographs.

Graphs on six vertices. There are eight forbidden induced subgraphs for apex
cographs on six vertices, namely, the $6$-vertex graphs shown in Figure 1 and
their complements.

Graphs on seven vertices. There are $62$ forbidden induced subgraphs for apex
cographs on seven vertices, the graphs in Figure 2 and their complements.

Graphs on eight vertices. There are $75$ forbidden induced subgraphs for apex
cographs on eight vertices, the graphs in Figure 3 and their complements. Note
that three out of these $75$ graphs are self-complementary.

Figure 1. These and their complements are the $6$-vertex forbidden induced
subgraphs for apex cographs.

Figure 2. These and their complements are the $7$-vertex forbidden induced
subgraphs for apex cographs.

Figure 3. These and their complements are the $8$-vertex forbidden induced
subgraphs for apex cographs.

Graphs on nine vertices. The algorithm found no 9-vertex forbidden induced
subgraphs. However, we felt it unsatisfactory to rely on a computer program
for such a significant fact, so we produced a readable proof by analyzing a
possible $9$-vertex forbidden induced subgraph for apex cographs, and ruling
out that possibility. That proof occupies the rest of the section. Henceforth,
$G$ denotes a $9$-vertex forbidden induced subgraph for apex cographs.

######  Lemma 3.2.

$V(G)$ has three distinct subsets $S,T,$ and $F$ such that each of $G[S]$,
$G[T],$ and $G[F]$ induces a path $P_{4}$, and $|S\cap T|=|T\cap F|=|S\cap
F|=1$.

###### Proof.

By Proposition 2.1, $G$ has distinct subsets $S$ and $T$ such that both $G[S]$
and $G[T]$ induce the path $P_{4}$, and $|S\cap T|=1$. Let $S\cap
T=\\{\alpha\\}$. Since $G-\alpha$ is not a cograph, there is a subset $F$ of
$V(G)-\alpha$ such that $G[F]\cong P_{4}$. Since $V(G)=S\cup T\cup F$, we have
$|T\cap F|=|S\cap F|=1$. ∎

Note that $|S\cap T\cap F|=0$, otherwise $|V(G)|>9$.

In the rest of the section we let $S=\\{\alpha,s_{1},s_{2},\beta\\}$,
$T=\\{\alpha,t_{1},t_{2},\gamma\\},$ and $F=\\{\beta,f_{1},f_{2},\gamma\\}$
denote the subsets of $V(G)$ as in Lemma 3.2. Thus,
$V(G)=\\{\alpha,\beta,\gamma,s_{1},s_{2},t_{1},t_{2},f_{1},f_{2}\\}$.

######  Lemma 3.3.

Let $\\{x,y\\}=\\{\alpha,f_{1}\\},\\{\alpha,f_{2}\\}$,
$\\{\beta,t_{1}\\},\\{\beta,t_{2}\\},\\{\gamma,s_{1}\\}$, or
$\\{\gamma,s_{2}\\}$. Then $G-\\{x,y\\}$ is a cograph.

###### Proof.

For $i=1,2$, the graph $G-f_{i}$ is an apex cograph, so it has a vertex $z$ in
$V(G)-f_{i}$ such that $G-\\{f_{i},z\\}$ is a cograph. We must have
$z=\alpha$; otherwise $V(G)-\\{f_{i},z\\}$ would contain $S$ or $T$, thus an
induced $P_{4}$, a contradiction. Replacing $f_{i}$ with $t_{i}$, our result
follows for $\\{\beta,t_{i}\\}$, and similarly for $\\{\gamma,s_{i}\\}$. ∎

For two $P_{4}$’s that have one common vertex, there are three distinct cases
based on how they intersect with each other. The cases are shown in Figure 4;
we call them the $L$-case, $T$-case, and $X$-case as in the figure.

Figure 4. The intersection cases of two $P_{4}$’s.

######  Lemma 3.4.

Let $S$ and $T$ be distinct subsets of $V(G)$ as in Lemma 3.2. If the
intersection of $G[S]$ and $G[T]$ is an $L$-case, then for $i=1,2$ the graph
$G-\\{\alpha,f_{i}\\}$ is connected.

###### Proof.

We denote the intersection of $G[S]$ and $G[T]$ as shown in Figure 5, where
$\\{1,2,3\\}=\\{s_{1},s_{2},\beta\\}$ and
$\\{4,5,6\\}=\\{t_{1},t_{2},\gamma\\}$. First suppose that there is no edge
between $\\{1,2,3\\}$ and $\\{4,5,6\\}$ in $G$, so $1\alpha 45$ and $4\alpha
12$ are $P_{4}$’s in $G$. By Lemma 3.3, it follows that $1=\beta$ or
$6=\gamma$, and $4=\gamma$ or $3=\beta$. Note that if $6=\gamma$, then
$1\alpha 45$ is a $P_{4}$ in $G-\\{\gamma,s\\}$ for $s=s_{1}$ or $s_{2}$, a
contradiction to Lemma 3.3. Similarly, if $3=\beta$, then $4\alpha 12$ is a
$P_{4}$ in $G-\\{\beta,t\\}$ for $t=t_{1}$ or $t_{2}$ contradicting Lemma 3.3.
Therefore $1=\beta$ and $4=\gamma$.

For $\\{i,j\\}=\\{1,2\\}$, observe that if $f_{j}$ has both $\gamma$ and
$\beta$ as its neighbours in $G$, then $G-\\{\alpha,f_{i}\\}$ is connected and
our result follows. Since $\gamma\beta$ is not an edge in $G$, we may assume
that the $P_{4}$ induced on $\\{\beta,\gamma,f_{i},f_{j}\\}$ is $\beta
f_{i}f_{j}\gamma$ or $\beta f_{i}\gamma f_{j}$. If $\beta f_{i}f_{j}\gamma$ is
a $P_{4}$ in $G$, then $f_{i}2$ is an edge in $G$ otherwise $f_{j}f_{i}\beta
2$ is a $P_{4}$ in $G-\\{\gamma,s\\}$ for $s=s_{1}$ or $s_{2}$, a
contradiction to Lemma 3.3. Also $f_{i}3$ is an edge in $G$, else
$f_{j}f_{i}23$ is a $P_{4}$ in $G-\\{\beta,t\\}$ for $t=t_{1}$ or $t_{2}$. It
follows that $\gamma f_{j}f_{i}3$ is a $P_{4}$ in $G-\\{\beta,t\\}$ for
$t=t_{1}$ or $t_{2}$, a contradiction to Lemma 3.3. Therefore $\beta
f_{i}\gamma f_{j}$ is a $P_{4}$ in $G$. Observe that $f_{i}2$ is an edge in
$G$, else $\gamma f_{i}\beta 2$ is a $P_{4}$ in $G-\\{\alpha,f_{j}\\}$, a
contradiction to Lemma 3.3. Also $f_{i}3$ is an edge in $G$, else $\gamma
f_{i}23$ is a $P_{4}$ in $G-\\{\alpha,f_{j}\\}$, again a contradiction to
Lemma 3.3. It follows that $f_{j}\gamma f_{i}3$ is a $P_{4}$ in
$G-\\{\beta,t\\}$ for $t=t_{1}$ or $t_{2}$, a contradiction. Therefore, there
is an edge between $\\{1,2,3\\}$ and $\\{4,5,6\\}$.

We may assume that the $P_{4}$ induced on $\\{f_{i},f_{j},\gamma,\beta\\}$ is
$f_{j}f_{i}\beta\gamma$, and $f_{j}$ has no neighbour in
$\\{\beta,\gamma,s_{1},s_{2},t_{1},t_{2}\\}$ in $G$, otherwise we have our
result. Observe that, for a neighbour $x$ of $f_{i}$ in $\\{1,2,3\\}$, a
neighbour $v$ of $x$ in $\\{1,2,3\\}$ is also a neighbour of $f_{i}$ in $G$;
otherwise $f_{j}f_{i}xv$ is a $P_{4}$ in $G-\\{\gamma,s\\}$ or
$G-\\{\beta,t\\}$ where $s$ is in $\\{s_{1},s_{2}\\}$ and $t$ is in
$\\{t_{1},t_{2}\\}$, a contradiction to Lemma 3.3. It follows that $f_{i}$ is
a neighbour of every vertex in $\\{1,2,3\\}$ in $G$. Note that $f_{j}\alpha$
is not an edge in $G$; otherwise $f_{j}\alpha 45$ would be a $P_{4}$ in
$G-\\{\gamma,s\\}$ or $G-\\{\beta,t\\}$ where $s$ is in $\\{s_{1},s_{2}\\}$
and $t$ is in $\\{t_{1},t_{2}\\}$, a contradiction to Lemma 3.3. Observe that
if $f_{i}\alpha$ is not an edge in $G$, then $f_{j}f_{i}1\alpha$ is a $P_{4}$
in $G-\\{\gamma,s\\}$ for $s=s_{1}$ or $s_{2}$, contradicting Lemma 3.3.
Therefore $f_{i}\alpha$ is an edge in $G$. If $f_{i}4$ is not an edge in $G$,
then $f_{j}f_{i}\alpha 4$ is a $P_{4}$ in $G-\\{\beta,t\\}$ for $t=t_{1}$ or
$t_{2}$, a contradiction. Observe that $f_{i}5$ is also an edge in $G$;
otherwise $f_{j}f_{i}45$ is a $P_{4}$ in $G-\\{\gamma,s\\}$ or
$G-\\{\beta,t\\}$ where $s$ is in $\\{s_{1},s_{2}\\}$ and $t$ is in
$\\{t_{1},t_{2}\\}$, a contradiction. Since $f_{i}\gamma$ is not an edge in
$G$, it follows that $6=\gamma$, so $f_{j}f_{i}56$ is a $P_{4}$ in
$G-\\{\beta,t\\}$ for $t=t_{1}$ or $t_{2}$, a contradiction to Lemma 3.3.
Therefore our result holds. ∎

Figure 5. Intersection of $G[S]$ and $G[T]$.

######  Lemma 3.5.

Let $S$, $T,$ and $F$ be distinct subsets of $V(G)$ as in Lemma 3.2. Then
there is at least one pair in $\\{G[S],G[T],G[F]\\}$ whose intersection is not
a $T$-case.

###### Proof.

Assume that the intersection of every pair in $\\{G[S],G[T],G[F]\\}$ is a
$T$-case. Then we have six distinct cases depending upon how $G[S]$, $G[T],$
and $G[F]$ intersect with each other in $G$. The cases are shown in Figure 6.
Observe that the cases $1$, $2,$ and $3$ are complementary to cases $4$, $5,$
and $6$, respectively. By Lemma 3.1, it is enough to consider case 1, case 2,
and case 3.

Suppose that the intersection of $G[S]$, $G[T],$ and $G[F]$ is case 1; then
the intersection of $\overline{G}[S]$, $\overline{G}[T],$ and
$\overline{G}[F]$ is case 4. Observe that if there is no edge between $t_{2}$
and $\\{s_{1},s_{2}\\}$ in $G$, then $t_{2}\alpha s_{1}s_{2}$ is a $P_{4}$ in
$G-\\{\beta,t_{1}\\}$, a contradiction to Lemma 3.3. Similarly, if there is no
edge between $\\{s_{1},s_{2}\\}$ and $\\{\gamma,t_{1}\\}$, then $\gamma\alpha
s_{1}s_{2}$ is a $P_{4}$ in $G-\\{\beta,t_{1}\\}$, a contradiction. Therefore
$G-\\{\alpha,f_{2}\\}$ is connected. If there is no edge between $s_{2}$ and
$\\{t_{1},t_{2}\\}$ in $\overline{G}$, then $s_{2}\alpha t_{1}t_{2}$ is a
$P_{4}$ in $\overline{G}-\\{\gamma,s_{1}\\}$, a contradiction to Lemma 3.3.
Therefore $\overline{G}-\\{\alpha,f_{2}\\}$ is connected. This contradicts
Lemma 3.3 since $G-\\{\alpha,f_{2}\\}$ is a cograph.

Next suppose that the intersection of $G[S]$, $G[T],$ and $G[F]$ is case 2.
Observe that if there is no edge between $s_{2}$ and $\\{t_{2},\gamma\\}$ in
$G$, then $s_{2}\alpha t_{2}\gamma$ is a $P_{4}$ in $G-\\{\beta,t_{1}\\}$, a
contradiction to Lemma 3.3. Similarly, there is an edge between $s_{1}$ and
$\\{t_{2},\gamma\\}$ in $G$, so $G-\\{\alpha,f_{2}\\}$ is connected. Observe
that if there is no edge between $t_{1}$ and $\\{\beta,s_{1}\\}$ in
$\overline{G}$, then $t_{1}\alpha\beta s_{1}$ is a $P_{4}$ in
$G-\\{\gamma,s_{2}\\}$, a contradiction to Lemma 3.3. Therefore
$\overline{G}-\\{\alpha,f_{2}\\}$ is connected, a contradiction.

Finally suppose that the intersection of $G[S]$, $G[T],$ and $G[F]$ is case 3.
If there is no edge between $s_{1}$ and $\\{t_{2},\gamma\\}$ in $G$, then
$s_{1}\alpha t_{2}\gamma$ is a $P_{4}$ in $G-\\{\beta,t_{1}\\}$, a
contradiction to Lemma 3.3. It follows that $G-\\{\alpha,f_{1}\\}$ is
connected. If $t_{1}$ has no edge to $\beta,s_{1}$ in $\overline{G}$, then
$t_{1}\alpha\beta s_{1}$ is a $P_{4}$ in $G-\\{\gamma,s_{2}\\}$, a
contradiction. By Lemma 3.3, $\overline{G}-\\{\alpha,f_{1}\\}$ is
disconnected, so we may assume that there is no edge between $f_{2}$ and
$\\{t_{1},t_{2}\\}$ in $\overline{G}$. It follows that either
$f_{2}\gamma\alpha t_{1}$ or $f_{2}\alpha t_{1}t_{2}$ is a $P_{4}$ in
$\overline{G}$. Then $f_{2}\gamma\alpha t_{1}$ is a $P_{4}$ in
$\overline{G}-\\{\beta,t_{2}\\}$, a contradiction to Lemma 3.3, and
$f_{2}\alpha t_{1}t_{2}$ is a $P_{4}$ in $\overline{G}-\\{\gamma,s_{1}\\}$,
again a contradiction to Lemma 3.3. Therefore
$\overline{G}-\\{\alpha,f_{1}\\}$ is connected. This is a contradiction, so
our result holds. ∎

Figure 6. The distinct cases where all intersections are $T$-cases.

######  Proposition 3.6.

There is no $9$-vertex forbidden induced subgraph for apex cographs.

###### Proof.

Assume that $G$ is a $9$-vertex forbidden induced subgraph for apex cographs.
Let $S,T,$ and $F$ be distinct subsets of $V(G)$ as in Lemma 3.2. By Lemma 3.1
and Lemma 3.5, we may assume that the intersection of $G[S]$ and $G[T]$ is an
$L$-case, as shown in Figure 7. The intersection of $\overline{G}[S]$ and
$\overline{G}[T]$ is an $X$-case. By Lemma 3.4, for $i$ in $\\{1,2\\}$ the
graph $G-\\{\alpha,f_{i}\\}$ is connected, so by Lemma 3.3, the complement
$\overline{G}-\\{\alpha,f_{i}\\}$ is disconnected.

Suppose that there is no edge between $\\{1,2\\}$ and $\\{5,6\\}$ in
$\overline{G}$. Then $2\alpha 56$ and $5\alpha 21$ are $P_{4}$’s in
$\overline{G}$. Observe that, if $2\neq\beta$ then $4=\gamma$ and $2\alpha 56$
is a $P_{4}$ in $\overline{G}-\\{\gamma,s\\}$ for $s=s_{1}$ or $s_{2}$, a
contradiction to Lemma 3.3. Therefore $2=\beta$. By symmetry, $5=\gamma$. If
there is no edge between $\\{3\\}$ and $\\{\gamma,6\\}$ in $\overline{G}$,
then $3\alpha\gamma 6$ is a $P_{4}$ in $\overline{G}-\\{\beta,t\\}$ for
$t=t_{1}$ or $t_{2}$, a contradiction to Lemma 3.3. Therefore there is an edge
between $\\{3\\}$ and $\\{\gamma,6\\}$ in $\overline{G}$. Similarly, there is
an edge between $\\{4\\}$ and $\\{1,\beta\\}$ in $\overline{G}$. For
$\\{i,j\\}=\\{1,2\\}$, if $f_{i}$ has neighbours in $\\{1,\beta\\}$ and
$\\{\gamma,6\\}$ in $\overline{G}$, then $\overline{G}-\\{\alpha,f_{j}\\}$ is
connected, a contradiction. Therefore $f_{i}$ has no neighbour in
$\\{1,\beta\\}$ or $\\{\gamma,6\\}$ in $\overline{G}$. Similarly, $f_{j}$ has
no neighbour in $\\{1,\beta\\}$ or $\\{\gamma,6\\}$ in $\overline{G}$. Since
$\\{\beta,\gamma,f_{1},f_{2}\\}$ induces a $P_{4}$, we may assume that the
$P_{4}$ is $\gamma f_{i}f_{j}\beta$. Note that $f_{j}$ has no neighbour in
$\\{3,\gamma,6\\}$ in $\overline{G}$, and $f_{i}$ has no neighbour in
$\\{1,\beta,4\\}$ in $\overline{G}$. It follows that either $4\alpha\gamma
f_{i}$ is a $P_{4}$ in $\overline{G}$, or $\alpha f_{i}$ is an edge in
$\overline{G}$. Thus, $4\alpha\gamma f_{i}$ is a $P_{4}$ in
$\overline{G}-\\{\beta,t\\}$ for $t=t_{1}$ or $t_{2}$. This is a contradiction
to Lemma 3.3 so we may assume that $\alpha f_{i}$ is an edge. It follows that
$1\beta\alpha f_{i}$ is a $P_{4}$ in $\overline{G}-\\{\gamma,s\\}$ for
$s=s_{1}$ or $s_{2}$, a contradiction. Therefore we may assume that there is
an edge between $\\{1,2\\}$ and $\\{5,6\\}$ in $\overline{G}$.

Suppose that there is no edge between $\\{3\\}$ and $\\{5,6\\}$ in
$\overline{G}$. Then $3\alpha 56$ is a $P_{4}$, so by Lemma 3.3 we have
$3=\beta$ or $4=\gamma$. If $4=\gamma$, then $3\alpha 56$ is a $P_{4}$ in
$\overline{G}-\\{\gamma,s\\}$ for $s=s_{1}$ or $s_{2}$, a contradiction to
Lemma 3.3. Therefore $3=\beta$ and $4\neq\gamma$. If there is no edge between
$\\{4\\}$ and $\\{1,2\\}$ in $\overline{G}$, then $4\alpha 21$ is a $P_{4}$ in
$\overline{G}-\\{\beta,t\\}$ where $t$ is in $\\{t_{1},t_{2}\\}$, a
contradiction to Lemma 3.3. Therefore there is an edge between $\\{4\\}$ and
$\\{1,2\\}$ in $\overline{G}$. Since $\gamma\in\\{5,6\\}$ and there is no edge
between $\\{3\\}$ and $\\{5,6\\}$ in $\overline{G}$, it follows that
$\gamma\beta$ is not an edge in $\overline{G}$. Observe that
$\\{\gamma,\beta,f_{i},f_{j}\\}$ induces a $P_{4}$ in $\overline{G}$ so both
$\gamma$ and $\beta$ have a neighbour in $\\{f_{i},f_{j}\\}$ in
$\overline{G}$. If both $\gamma$ and $\beta$ are neighbours of $f_{i}$ in
$\overline{G}$, then $\overline{G}-\\{\alpha,f_{j}\\}$ is connected, a
contradiction.

Since $\beta\gamma$ is not an edge in $\overline{G}$, it follows that the
$P_{4}$ induced by $\\{\gamma,\beta,f_{i},f_{j}\\}$ in $\overline{G}$ is
$\beta f_{i}f_{j}\gamma$ or $\beta f_{j}f_{i}\gamma$. In the former case
$f_{i}$ has no neighbour in $\\{5,6\\}$ in $\overline{G}$, else
$\overline{G}-\\{\alpha,f_{j}\\}$ would be connected, a contradiction. It
follows that $f_{i}\beta\alpha 5$ is a $P_{4}$ unless $\alpha f_{i}$ is an
edge in $\overline{G}$. Now $f_{i}\beta\alpha 5$ is a $P_{4}$ in
$\overline{G}-\\{\gamma,s\\}$ for $s=s_{1}$ or $s_{2}$. This contradicts Lemma
3.3, so $\alpha f_{i}$ is an edge in $\overline{G}$. It follows that
$f_{i}\alpha 56$ is a $P_{4}$ in $\overline{G}-\\{\beta,t\\}$ for $t$ in
$\\{t_{1},t_{2}\\}$, a contradiction to Lemma 3.3. Therefore in the former
case there is an edge between $\\{3\\}$ and $\\{5,6\\}$ in $\overline{G}$. The
latter case is similar.

Similarly, there is an edge between $\\{4\\}$ and $\\{1,2\\}$ in
$\overline{G}$.

It now follows that $\overline{G}-\\{\alpha,f\\}$ is connected for $f$ in
$\\{f_{1},f_{2}\\}$, a contradiction. This completes the proof that there is
no 9-vertex forbidden induced subgraph. ∎

Figure 7. $L$-case intersection of $G[S]$ and $G[T]$, where $S=\\{1,2,3\\}$
and $T=\\{4,5,6\\}$.

## Declarations

V. Sivaraman was partially supported by Simons Foundation Travel Support for
Mathematicians (Award No. 855469). All relevant data are included in this
article.

## References

  * [1] D.G. Corneil, H. Lerchs, and L. Stewart Burlingham, Complement reducible graphs, Discrete Appl. Math. 3 (1981), 163–174.
  * [2] D.G. Corneil, Y. Perl, and L.K. Stewart, A linear recognition for cographs, SIAM J. Comput. 14 (1985), 926–934. bibitemjung H.A. Jung, On a class of posets and the corresponding comparability graphs, J. Combin. Theory Ser. B 24 (1978), 125–133.
  * [3] B.D. McKay and A. Piperno, Practical graph isomorphism II, J. Symbolic Comput. 60 (2014), 94–112.
  * [4] SageMath, the Sage Mathematics Software System (Version 8.2), The Sage Developers, 2019, http://www.sagemath.org.
  * [5] D. Seinsche, On a property of the class of $n$-colourable graphs, J. Combin. Theory Ser. B 16 (1974), 191–193.