# Bisimplicial separators

Martin Milanič FAMNIT and IAM, University of Primorska, Koper, Slovenia.
Email<EMAIL_ADDRESS>Partially supported by the Slovenian Research
Agency (I0-0035, research program P1-0285 and research projects N1-0102,
N1-0160, J1-3001, J1-3002, J1-3003, J1-4008, and J1-4084). Irena Penev
Computer Science Institute of Charles University (IÚUK), Prague, Czech
Republic. Email<EMAIL_ADDRESS>Nevena Pivač FAMNIT and IAM,
University of Primorska, Koper, Slovenia. Email<EMAIL_ADDRESS>Partially supported by the Slovenian Research Agency (research program
P1-0285, research projects N1-0102 and J1-4008, and a Young Researchers
Grant). Kristina Vušković School of Computing, University of Leeds, Leeds, UK.
Email<EMAIL_ADDRESS>Partially supported by EPSRC grant
EP/V002813/1.

###### Abstract

A _minimal separator_ of a graph $G$ is a set $S\subseteq V(G)$ such that
there exist vertices $a,b\in V(G)\setminus S$ with the property that $S$
separates $a$ from $b$ in $G$, but no proper subset of $S$ does. For an
integer $k\geq 0$, we say that a minimal separator is _$k$ -simplicial_ if it
can be covered by $k$ cliques and denote by $\mathcal{G}_{k}$ the class of all
graphs in which each minimal separator is $k$-simplicial. We show that for
each $k\geq 0$, the class $\mathcal{G}_{k}$ is closed under induced minors,
and we use this to show that the Maximum Weight Stable Set problem can be
solved in polynomial time for $\mathcal{G}_{k}$. We also give a complete list
of minimal forbidden induced minors for $\mathcal{G}_{2}$. Next, we show that,
for $k\geq 1$, every nonnull graph in $\mathcal{G}_{k}$ has a $k$-simplicial
vertex, i.e., a vertex whose neighborhood is a union of $k$ cliques; we deduce
that the Maximum Weight Clique problem can be solved in polynomial time for
graphs in $\mathcal{G}_{2}$. Further, we show that, for $k\geq 3$, it is NP-
hard to recognize graphs in $\mathcal{G}_{k}$; the time complexity of
recognizing graphs in $\mathcal{G}_{2}$ is unknown. We also show that the
Maximum Clique problem is NP-hard for graphs in $\mathcal{G}_{3}$. Finally, we
prove a decomposition theorem for diamond-free graphs in $\mathcal{G}_{2}$
(where the _diamond_ is the graph obtained from $K_{4}$ by deleting one edge),
and we use this theorem to obtain polynomial-time algorithms for the Vertex
Coloring and recognition problems for diamond-free graphs in
$\mathcal{G}_{2}$, and improved running times for the Maximum Weight Clique
and Maximum Weight Stable Set problems for this class of graphs.

Keywords: minimal separators, bisimplicial separators, induced minors, graph
algorithms

##  1 Introduction

All graphs in this paper are finite, simple, and undirected. Our graphs may
possibly be null. For a graph $G$ and nonadjacent vertices $a,b\in V(G)$,

  * •

an _$(a,b)$ -separator_ of $G$ is a set $S\subseteq V(G)\setminus\\{a,b\\}$
such that $a$ and $b$ belong to distinct components of $G\setminus S$;

  * •

a _minimal $(a,b)$-separator_ of $G$ is an $(a,b)$-separator $S$ of $G$ such
that no proper subset of $S$ is an $(a,b)$-separator of $G$.

For a graph $G$, a set $S\subseteq V(G)$ is a _separator_ (resp.  _minimal
separator_) of $G$ if there exist distinct, nonadjacent vertices $a,b\in
V(G)\setminus S$ such that $S$ is an $(a,b)$-separator (resp. minimal
$(a,b)$-separator) of $G$. Note that it is possible that $S$ is a minimal
separator of a graph $G$, even though some $S^{\prime}\subsetneqq S$ is also a
separator of $G$. Indeed, there may be a pair $a,b$ of nonadjacent vertices
such that $S$ is a minimal $(a,b)$-separator of $G$, as well as some other
pair $a^{\prime},b^{\prime}$ of nonadjacent vertices such that some
$S^{\prime}\subsetneqq S$ is an $(a^{\prime},b^{\prime})$-separator of $G$.

A graph is _chordal_ if it contains no induced cycles of length greater than
three. Minimal separators have been studied since at least the 1960s, when
chordal graphs were characterized as precisely those graphs in which all
minimal separators are cliques [18]. Minimal separators were subsequently
studied in [6] in the context of moplexes, have played an important role in
sparse matrix computations via minimal triangulations (for a survey, see
[23]), and have also had numerous algorithmic applications (see, e.g., [4, 8,
10, 28]). This paper is a contribution to the study of minimal separators.

For a class $\mathcal{C}$ of graphs, we denote by $\mathcal{G}_{\mathcal{C}}$
the class of all graphs $G$ such that every minimal separator of $G$ induces a
graph from $\mathcal{C}$. Since complete graphs have no separators, we see for
all classes $\mathcal{C}$, the class $\mathcal{G}_{\mathcal{C}}$ contains all
complete graphs (including the null graph). For a nonnegative integer $k$, we
denote by $\mathcal{G}_{k}$ the class of all graphs $G$ that have the property
that every minimal separator of $G$ is a union of $k$ (possibly empty)
cliques.111Clearly, given a graph $G$ and a set $S\subseteq V(G)$, the set $S$
is a union of $k$ cliques if and only if $S$ is a union of $k$ pairwise
disjoint cliques. Obviously,
$\mathcal{G}_{0}\subseteq\mathcal{G}_{1}\subseteq\mathcal{G}_{2}\subseteq\dots$,
and all these inclusions are proper, as verified by the class of complete
bipartite graphs with exactly two vertices in one part. Note that
$\mathcal{G}_{0}$ is the class of all disjoint unions of (arbitrarily many)
complete graphs, and (by [18]) $\mathcal{G}_{1}$ is the class of all chordal
graphs. For a nonnegative integer $k$, we denote by $\mathcal{C}_{k}$ the
class of all graphs whose vertex sets can be partitioned into $k$ (possibly
empty) cliques; clearly, $\mathcal{G}_{k}=\mathcal{G}_{\mathcal{C}_{k}}$.

In this paper, we prove a number of results about classes of the form
$\mathcal{G}_{\mathcal{C}}$, where $\mathcal{C}$ is a hereditary class. We
place particular emphasis on the class $\mathcal{G}_{2}$. By the above,
$\mathcal{G}_{2}$ contains all chordal graphs. Moreover, it is easy to see
that all circular-arc graphs (that is, intersection graphs of arcs on a
circle) belong to $\mathcal{G}_{2}$.

In Section 2, we prove some basic properties of the class
$\mathcal{G}_{\mathcal{C}}$, when $\mathcal{C}$ satisfies various hypotheses.

In Section 3, we focus on hereditary graph classes that are closed under edge
addition. We show that for any such class $\mathcal{C}$, both the class
$\mathcal{C}$ and the corresponding class $\mathcal{G}_{\mathcal{C}}$ are
closed under induced minors, and we characterize the class
$\mathcal{G}_{\mathcal{C}}$ in terms of forbidden induced minors. In the case
when $\mathcal{C}$ is also closed under the addition of universal vertices,
the class of _minimal_ forbidden induced minors for
$\mathcal{G}_{\mathcal{C}}$ is described precisely. As a consequence of these
results, we obtain that the classes $\mathcal{G}_{k}$ ($k\geq 0$) are closed
under induced minors and give a complete list of minimal forbidden induced
minors for the class $\mathcal{G}_{2}$. Combining these results with some
results from the literature [15, 22], we show that for every integer $k\geq
0$, the Maximum Weight Stable Set Problem can be solved in polynomial time for
graphs in $\mathcal{G}_{k}$, and we further show that all 1-perfectly-
orientable graphs belong to $\mathcal{G}_{2}$.

In Section 4, we show that for every $k\geq 1$, every nonnull graph in
$\mathcal{G}_{k}$ has a $k$-simplicial vertex (i.e., a vertex whose
neighborhood is a union of $k$ cliques). We do this by showing that every
LexBFS ordering of a graph in $\mathcal{G}_{k}$ is a $k$-simplicial
elimination ordering.222We postpone the statements of precise definitions to
Section 4. This generalizes a result by Rose, Tarjan, and Lueker on chordal
graphs [27], which corresponds to the case $k=1$ Using [30] we deduce that the
Maximum Weight Clique problem can be solved in polynomial time for graphs in
$\mathcal{G}_{2}$.

In Section 5, we show that for each $k\geq 3$, it is NP-hard to recognize
graphs in $\mathcal{G}_{k}$; the time complexity of recognizing graphs in
$\mathcal{G}_{2}$ is unknown. We further show that the Maximum Clique problem
is NP-hard for $\mathcal{G}_{3}$ (and consequently for $\mathcal{G}_{k}$
whenever $k\geq 3$). Note that, since Vertex Coloring is NP-hard for circular-
arc graphs [21], which form a subclass of $\mathcal{G}_{2}$, the problem is
also NP-hard for $\mathcal{G}_{k}$, whenever $k\geq 2$.

The _diamond_ is the four-vertex graph obtained from the complete graph
$K_{4}$ by deleting one edge. In Section 6, we prove a decomposition theorem
for diamond-free graphs in $\mathcal{G}_{2}$, and use this theorem to obtain
polynomial-time algorithms for the Vertex Coloring and recognition problems
for diamond-free graphs in $\mathcal{G}_{2}$, and improved running times for
the Maximum Weight Clique and Maximum Weight Stable Set problems in this class
of graphs.

Table 1 summarizes our algorithmic and complexity results. Since
$\mathcal{G}_{0}$ is the class of all disjoint unions of complete graphs, and
$\mathcal{G}_{1}$ is the class of all chordal graphs, all problems from the
table below can be solved in linear time for $\mathcal{G}_{0}$ and
$\mathcal{G}_{1}$ (see [27, 20]).

| diamond-free |  |
---|---|---|---
| graphs in $\mathcal{G}_{2}$ | $\mathcal{G}_{2}$ |  $\mathcal{G}_{k}$ ($k\geq 3$)
recognition | $\mathcal{O}(n^{\omega}\log n)$ | ? | NP-hard
Maximum Weight Clique | $\mathcal{O}(n^{\omega}\log n)$ | $\mathcal{O}(n^{3+o(1)})$ | NP-hard
Maximum Weight Stable Set | $\mathcal{O}(n^{2}(n+m))$ | $\mathcal{O}(n^{6})$ | $\mathcal{O}(n^{2k+2})$
Vertex Coloring | $\mathcal{O}(n^{\omega}\log n)$ | NP-hard | NP-hard
Table 1: Summary of our algorithmic and complexity results. The number of
vertices and edges of the input graph are denoted by $n$ and $m$,
respectively, and $\omega<2.3728596$ denotes the matrix multiplication
exponent (see [2]).

###  1.1 Terminology and notation

The vertex set and the edge set of a graph $G$ are denoted by $V(G)$ and
$E(G)$, respectively. The complement of $G$ is denoted by $\overline{G}$.

A _clique_ in a graph $G$ is a (possibly empty) set of pairwise adjacent
vertices, and a _stable set_ in $G$ is a (possibly empty) set of pairwise
nonadjacent vertices. Given a graph $G$ and a vertex $x\in V(G)$, we denote by
$N_{G}(x)$ the set of all neighbors of $x$ in $G$, and we set
$N_{G}[x]:=\\{x\\}\cup N_{G}(x)$. For a nonnegative integer $k$, a vertex
$x\in V(G)$ is _$k$ -simplicial_ in $G$ if $N_{G}(x)$ is the union of $k$
cliques. A $1$-simplicial vertex is also called _simplicial_ , and a
$2$-simplicial vertex is also called _bisimplicial_. Analogously, for a graph
$G$ and a set $X\subseteq V(G)$, we say that $X$ is _$k$ -simplicial_ in $G$
if it is a union of $k$ cliques and _bisimplicial_ if it is $2$-simplicial. In
particular, a graph $G$ belongs to the class $\mathcal{G}_{k}$ if and only if
every minimal separator of $G$ is $k$-simplicial, and to $\mathcal{G}_{2}$ if
and only if every minimal separator of $G$ is bisimplicial.

We say that a graph $H$ is an _induced subgraph_ of a graph $G$ if $H$ can be
obtained from $G$ via a (possibly null) sequence of vertex deletions. Given
graphs $H$ and $G$, we say that $G$ is _$H$ -free_ if no induced subgraph of
$G$ is isomorphic to $H$. For a graph $G$ and a set $X\subseteq V(G)$, we
denote by $G[X]$ the subgraph of $G$ induced by $X$; if
$X=\\{x_{1},\dots,x_{t}\\}$, we sometimes write $G[x_{1},\dots,x_{t}]$ instead
of $G[X]$. Furthermore, $G\setminus X$ is the graph obtained from $G$ by
deleting all vertices in $X$, i.e., $G\setminus X:=G[V(G)\setminus X]$; if
$X=\\{x\\}$, we sometimes write $G\setminus x$ instead of $G\setminus X$. A
_path_ in $G$ is a nonempty sequence $p_{1},\ldots,p_{k}$ of pairwise distinct
vertices of $G$ such that $p_{i}$ and $p_{i+1}$ are adjacent for all
$i\in\\{1,\ldots,k-1\\}$.

For a nonnegative integer $n$, we denote by $K_{n}$, $P_{n}$, and $C_{n}$,
respectively, the complete graph, path graph, and cycle graph on $n$ vertices.
For two nonnegative integers $p$ and $q$, we denote by $K_{p,q}$ the complete
bipartite graph with parts of size $p$ and $q$. A class $\mathcal{C}$ of
graphs is _hereditary_ if for all $G\in\mathcal{C}$, all (isomorphic copies
of) induced subgraphs of $G$ belong to $\mathcal{C}$.

Given a graph $G$ and an edge $e=xy\in E(G)$, _subdividing_ the edge $e$ means
replacing $e$ with a path of length two, that is, removing the edge $e$ and
adding a new vertex $z$ adjacent to precisely $x$ and $y$. A _subdivision_ of
a graph $G$ is any graph obtained from $G$ by a (possibly null) sequence of
edge subdivisions. Given a graph $G$ and an edge $e\in E(G)$, _contracting_
the edge $e=xy$ means replacing the vertices $x$ and $y$ in $G$ with a new
vertex $v^{xy}$ adjacent to every vertex that is adjacent in $G$ to $x$ or
$y$. We denote by $G/e$ the graph obtained from $G$ by contracting $e$. We say
that a graph $H$ is an _induced minor_ of a graph $G$ if $H$ can be obtained
from $G$ via a (possibly null) sequence of vertex deletions and edge
contractions. Given graphs $H$ and $G$, we say that $G$ is _$H$ -induced-
minor-free_ if no induced minor of $G$ is isomorphic to $H$. For a family
$\mathcal{H}$ of graphs, we say that a graph $G$ is _$\mathcal{H}$ -induced-
minor-free_ if $G$ is $H$-induced-minor-free for all graphs $H\in\mathcal{H}$.

Given two graphs $G$ and $H$, an _induced minor model_ of $H$ in $G$ is a
family $\\{X_{v}\\}_{v\in V(H)}$ of nonempty, pairwise disjoint subsets of
$V(G)$, each inducing a connected subgraph of $G$, and having the property
that for all distinct $u,v\in V(H)$, there is an edge between $X_{u}$ and
$X_{v}$ in $G$ if and only if $uv\in E(H)$. Note that $H$ is an induced minor
of $G$ if and only if $G$ admits an induced minor model of $H$.

Given a graph $G$, a vertex $x\in V(G)$, and a set $Y\subseteq
V(G)\setminus\\{x\\}$, we say that $x$ is _complete_ (resp.  _anticomplete_)
to $Y$ in $G$ if $x$ is adjacent (resp. nonadjacent) to all vertices in $Y$.
Given disjoint sets $A,B\subseteq V(G)$, we say that $A$ is _complete_ (resp.
_anticomplete_) to $B$ in $G$ if every vertex in $A$ is complete (resp.
anticomplete) to $B$ in $G$. A _universal vertex_ of a graph $G$ is a vertex
$u$ such that $N_{G}[u]=V(G)$. _Adding a universal vertex_ to a graph $G$
means adding a new vertex $v$ and making it adjacent to all vertices of $G$;
note that $v$ is a universal vertex in the resulting graph.

A _cutset_ of a graph $G$ is a (possibly empty) set $C\subseteq V(G)$ such
that $G\setminus C$ is disconnected. A _minimal cutset_ of a graph $G$ is a
cutset $C$ of $G$ such that no proper subset of $C$ is a cutset of $G$. A
_clique-cutset_ is a cutset that is a clique. Note that $\emptyset$ is a
clique-cutset of any disconnected graph.

A _cut-partition_ of a graph $G$ is a partition $(A,B,C)$ of $V(G)$ such that
$A$ and $B$ are nonempty and anticomplete to each other (the set $C$ may
possibly be empty). Note that if $(A,B,C)$ is a cut-partition of $G$, then $C$
is a cutset of $G$; conversely, every cutset of $G$ gives rise to at least one
cut-partition of $G$.

If $H_{1}$ and $H_{2}$ are graphs on disjoint vertex sets, the _disjoint
union_ of $H_{1}$ and $H_{2}$, denoted by $H_{1}\cup H_{2}$, is the graph with
vertex set $V(H_{1})\cup V(H_{2})$ and edge set $E(H_{1})\cup E(H_{2})$. More
generally, the operation of _gluing $H_{1}$ and $H_{2}$ along a clique_
produces a graph obtained from $H_{1}\cup H_{2}$ by choosing cliques $C_{1}$
in $H_{1}$ and $C_{2}$ in $H_{2}$ such that $|C_{1}|=|C_{2}|$, fixing a
bijection $f$ from $C_{1}$ to $C_{2}$, and identifying each vertex $v\in
C_{1}$ with the vertex $f(v)$.

Given a graph $G$ and a vertex weight function $w:V\to\mathbb{Q}_{+}$, the
Maximum Weight Clique problem is the problem of computing a clique $C$ in $G$
with maximum total weight, where the weight of a set $X\subseteq V(G)$ is
defined as $\sum_{x\in X}w(x)$. Similarly, the Maximum Weight Stable Set
problem is the problem of computing a stable set $S$ in $G$ with maximum total
weight. In the case of weight functions constantly equal to $1$, we obtain the
Maximum Clique and Maximum Stable Set problems, respectively. A graph
$G=(V,E)$ is _$k$ -colorable_ if $V$ is a union of $k$ stable sets in $G$.
Vertex Coloring is the following problem: given a graph $G$, compute its
_chromatic number_ $\chi(G)$, that is, the smallest integer $k$ such that $G$
is $k$-colorable. For a positive integer $k$, $k$-Coloring is the following
decision problem: given a graph $G$, determine whether $G$ is $k$-colorable.

##  2 Basic properties

Recall that for any graph class $\mathcal{C}$, we denote by
$\mathcal{G}_{\mathcal{C}}$ the class of all graphs $G$ such that every
minimal separator of $G$ induces a graph from $\mathcal{C}$. Note that if
$\mathcal{G}_{\mathcal{C}}$ is hereditary, then
$\mathcal{C}\subseteq\mathcal{G}_{\mathcal{C}}$. The following proposition
provides some equivalent characterizations of the class
$\mathcal{G}_{\mathcal{C}}$ for the case when ${\mathcal{C}}$ is hereditary.

######  Proposition 2.1.

Let $\mathcal{C}$ be a hereditary class of graphs, and let $G$ be a graph.
Then the following are equivalent:

  * (a)

$G\in\mathcal{G}_{\mathcal{C}}$;

  * (b)

for all induced subgraphs $H$ of $G$, every minimal separator $S$ of $H$
satisfies $H[S]\in\mathcal{C}$;

  * (c)

for all induced subgraphs $H$ of $G$, every minimal cutset $C$ of $H$
satisfies $H[C]\in\mathcal{C}$.

###### Proof.

We prove the result by showing that (a) implies (b), that (b) implies (c), and
that (c) implies (a).

First, we assume that (a) holds, and we prove (b). Let $H$ be an induced
subgraph of $G$, and suppose that $a,b\in V(H)$ are distinct, nonadjacent
vertices, and that $S$ is a minimal $(a,b)$-separator of $H$. Then
$S\cup(V(G)\setminus V(H))$ is an $(a,b)$-separator of $G$. Let
$S^{*}\subseteq S\cup(V(G)\setminus V(H))$ be a minimal $(a,b)$-separator of
$G$; by (a), $G[S^{*}]\in\mathcal{C}$. Since $S^{*}$ is an $(a,b)$-separator
of $G$, we have that $S^{*}\cap V(H)$ is an $(a,b)$-separator of $H$.
Moreover, $S^{*}\cap V(H)\subseteq S$, and so the minimality of $S$ guarantees
that $S^{*}\cap V(H)=S$; consequently, $S\subseteq S^{*}$. Since
$G[S^{*}]\in\mathcal{C}$, and since $\mathcal{C}$ is hereditary, it follows
that $G[S]\in\mathcal{C}$. Clearly, $G[S]=H[S]$, and so $H[S]\in\mathcal{C}$.
Thus, (b) holds.

Next, we assume that (b) holds, and we prove (c). Let $H$ be an induced
subgraph of $G$, and suppose that $C$ is a minimal cutset of $H$. Let $A$ and
$B$ be the vertex sets of two distinct components of $H\setminus C$. The
minimality of $C$ guarantees that every vertex in $C$ has a neighbor both in
$A$ and in $B$, and this, in turn, guarantees that for all $a\in A$ and $b\in
B$, $C$ is a minimal $(a,b)$-separator of $H$. But now (b) implies that
$H[C]\in\mathcal{C}$. Thus, (c) holds.

Finally, we assume that (c) holds, and we prove (a). Suppose that $a,b\in
V(G)$ are distinct, nonadjacent vertices, and that $S$ is a minimal
$(a,b)$-separator of $G$. Let $A$ (resp. $B$) be the vertex set of the
component of $G\setminus S$ that contains $a$ (resp. $b$). Clearly, $A$ and
$B$ are disjoint and anticomplete to each other. Furthermore, the minimality
of $S$ implies that every vertex in $S$ has a neighbor both in $A$ and in $B$.
Set $H:=G[A\cup B\cup S]$. Then $(A,B,S)$ is a cut-partition of $H$;
furthermore, since $H[A]$ and $H[B]$ are connected, and every vertex of $S$
has a neighbor both in $A$ and in $B$, we see that $S$ is a minimal cutset of
$H$. Now (c) guarantees that $H[S]\in\mathcal{C}$; since $H[S]=G[S]$, it
follows that $G[S]\in\mathcal{C}$. Thus, (a) holds. ∎

######  Corollary 2.2.

Let $\mathcal{C}$ be a hereditary class of graphs. Then
$\mathcal{G}_{\mathcal{C}}$ is hereditary.

###### Proof.

This readily follows from Proposition 2.1, and more precisely, from the
equivalence of (a) and (b) from Proposition 2.1. ∎

######  Theorem 2.3.

Let $\mathcal{C}$ be a hereditary class of graphs that contains all complete
graphs.333However, not all graphs in $\mathcal{C}$ need be complete. Then,
$\mathcal{G}_{\mathcal{C}}$ is closed under gluing along a clique.

###### Proof.

Let $G$ be a graph that admits a clique-cutset $C$ and let $(A,B,C)$ be an
associated cut-partition of $G$. Assume that $G_{A}:=G[A\cup C]$ and
$G_{B}:=G[B\cup C]$ both belong to $\mathcal{G}_{\mathcal{C}}$. It suffices to
show that $G\in\mathcal{G}_{\mathcal{C}}$.

Fix a pair of distinct, nonadjacent vertices $x,y\in V(G)$, and let $S$ be a
minimal $(x,y)$-separator of $G$. We must show that $G[S]\in\mathcal{C}$.
Since $C$ is a clique, it contains at most one of $x,y$; by symmetry, we may
therefore assume that $x\in A$. We now consider two cases: when $y\in A\cup
C$, and when $y\in B$.

Case 1: $y\in A\cup C$. Then $S\cap(A\cup C)$ is an $(x,y)$-separator of
$G_{A}$; let $S^{\prime}\subseteq S\cap(A\cup C)$ be a minimal
$(x,y)$-separator of $G_{A}$. Since $G_{A}\in\mathcal{G}_{\mathcal{C}}$, we
see that $G_{A}[S^{\prime}]=G[S^{\prime}]$ belongs to $\mathcal{C}$. If
$S^{\prime}=S$, then we are done. So, assume that $S^{\prime}\subsetneqq S$.
The minimality of $S$ then implies that there is a path $p_{1},\dots,p_{s}$ in
$G\setminus S^{\prime}$, with $p_{1}=x$ and $p_{s}=y$. Since $S^{\prime}$ is
an $(x,y)$-separator of $G_{A}$, we see that at least one vertex of the path
$p_{1},\dots,p_{s}$ belongs to $B$. Let $i$ be the smallest index in
$\\{1,\dots,s\\}$ such that $p_{i}\in B$, and let $j$ be the largest index in
$\\{1,\dots,s\\}$ such that $p_{j}\in B$. Since $p_{1},p_{s}\in A\cup C$, we
have that $2\leq i\leq j\leq s-1$. Moreover, since $A$ is anticomplete to $B$,
we have that $p_{i-1},p_{j+1}\in C$; since $C$ is a clique, we see that
$p_{i-1},p_{j+1}$ are adjacent. But now
$p_{1},\dots,p_{i-1},p_{j+1},\dots,p_{s}$ is a path between $x$ and $y$ in
$G_{A}\setminus S^{\prime}$, contrary to the fact that $S^{\prime}$ is an
$(x,y)$-separator of $G_{A}$.

Case 2: $y\in B$. Note that, in this case, $C$ is an $(x,y)$-separator of $G$.

Claim. At least one of $S\cap A$ and $S\cap B$ is empty.

_Proof of the Claim._ Suppose otherwise, i.e., that both $S\cap A$ and $S\cap
B$ are nonempty. Set $S_{A}:=S\setminus B$ and $S_{B}:=S\setminus A$. By the
minimality of $S$, there is a path $p_{1},\dots,p_{s}$, with $p_{1}=x$ and
$p_{s}=y$, in $G\setminus S_{A}$, and there is a path $q_{1},\dots,q_{t}$,
with $q_{1}=x$ and $q_{t}=y$, in $G\setminus S_{B}$. Since $p_{1}\in A$ and
$p_{s}\in B$, and since $A$ is anticomplete to $B$, some internal vertex of
the path $p_{1},\dots,p_{s}$ belongs to $C$; let $i$ be the smallest index in
$\\{2,\dots,s-1\\}$ such that $p_{i}\in C$ (then $p_{1},\dots,p_{i-1}\in A$).
Similarly, at least one internal vertex of the path $q_{1},\dots,q_{t}$
belongs to $C$; let $j$ be the largest index in $\\{2,\dots,t-1\\}$ such that
$q_{j}\in C$ (then $q_{j+1},\dots,q_{t}\in B$). Since $C$ is a clique, we see
that $p_{i}$ and $q_{j}$ are either equal or adjacent. In the former case,
$p_{1},\dots,p_{i},q_{j+1},\dots,q_{t}$ is a path between $x$ and $y$ in
$G\setminus S$; and in the latter case, $p_{1},\dots,p_{i},q_{j},\dots,q_{t}$
is a path between $x$ and $y$ in $G\setminus S$. But neither outcome is
possible, since $S$ is an $(x,y)$-separator of $G$. This proves the Claim.
$\blacklozenge$

By the Claim, and by symmetry, we may assume that $S\cap B=\emptyset$, i.e.,
$S\subseteq A\cup C$. Let $Y$ be the vertex set of the component of $G[B]$
that contains $y$.

Suppose first that $C\setminus S$ is anticomplete to $Y$. Then $C\cap S$ is an
$(x,y)$-separator of $G$, and so the minimality of $S$ guarantees that
$S\subseteq C$. Thus, $S$ is a clique; since $\mathcal{C}$ contains all
complete graphs, it follows that $G[S]\in\mathcal{C}$, and we are done.

From now on, we assume that $C\setminus S$ is not anticomplete to $Y$. Fix a
vertex $c\in C\setminus S$ that has a neighbor in $Y$. Since $y\in Y$, and
$G[Y]$ is connected, the graph $G$ contains a path $q_{1},\dots,q_{t}$, with
$q_{1}=c$, $q_{t}=y$, and $q_{2},\dots,q_{t}\in Y$ (so, $q_{2},\dots,q_{t}\in
B)$. Now, suppose that there is a path $p_{1},\dots,p_{s}$ in $G_{A}\setminus
S$, with $p_{1}=x$ and $p_{s}=c$. Then $p_{1},\dots,p_{s},q_{2},\dots,q_{t}$
is a path in $G\setminus S$ between $x$ and $y$, contrary to the fact that $S$
is an $(x,y)$-separator of $G$. So, $S$ is an $(x,c)$-separator of $G_{A}$.
Let $S^{\prime}\subseteq S$ be a minimal $(x,c)$-separator of $G_{A}$; since
$G_{A}\in\mathcal{G}_{\mathcal{C}}$, we see that
$G_{A}[S^{\prime}]=G[S^{\prime}]$ belongs to ${\mathcal{C}}$. If $S^{\prime}$
is an $(x,y)$-separator of $G$, then the minimality of $S$ guarantees that
$S=S^{\prime}$, and we are done. So, assume that $S^{\prime}$ is not an
$(x,y)$-separator of $G$. Then there is a path $r_{1},\dots,r_{k}$ in
$G\setminus S^{\prime}$, with $r_{1}=x$ and $r_{k}=y$. Since $x\in A$, $y\in
B$, and $A$ is anticomplete to $B$, we see that some internal vertex of
$r_{1},\dots,r_{k}$ belongs to $C$; let $i$ be the smallest index in
$\\{2,\dots,k-1\\}$ such that $r_{i}\in C$. Since $r_{i},c\in C$, and $C$ is a
clique, we see that $r_{i}$ and $c$ are either equal or adjacent. In the
former case, $r_{1},\dots,r_{i}$ is a path from $x$ to $c$ in $G_{A}\setminus
S^{\prime}$, and in the latter case, $r_{1},\dots,r_{i},c$ is a path from $x$
to $c$ in $G_{A}\setminus S^{\prime}$. But neither outcome is possible, since
$S^{\prime}$ is an $(x,c)$-separator of $G_{A}$. ∎

Theorem 2.3 implies the following result on the classes of graphs in which
every minimal separator is a union of $k$ cliques.

######  Corollary 2.4.

For every positive integer $k$, the class $\mathcal{G}_{k}$ is closed under
gluing along a clique.

###### Proof.

This follows immediately from Theorem 2.3, the fact that
$\mathcal{G}_{k}=\mathcal{G}_{\mathcal{C}_{k}}$, and the fact that the class
${\mathcal{C}_{k}}$ is a hereditary graph class containing all complete
graphs. ∎

Note that Corollary 2.4 fails for $\mathcal{G}_{0}$: the two-edge path $P_{3}$
is an obvious counterexample.

##  3 Forbidden induced minors

For a class of graphs $\mathcal{C}$, let us denote by
$\mathcal{M}_{\mathcal{C}}$ the class of all graphs that do not belong to
$\mathcal{C}$, but all of whose proper induced minors do belong to
$\mathcal{C}$. Note that nonisomorphic graphs in $\mathcal{M}_{\mathcal{C}}$
are incomparable under the induced minor relation. If the class $\mathcal{C}$
is closed under induced minors, then clearly, $\mathcal{C}$ is precisely the
class of all $\mathcal{M}_{\mathcal{C}}$-induced-minor-free graphs. In this
case, we refer to graphs in $\mathcal{M}_{\mathcal{C}}$ as the _minimal
forbidden induced minors_ for the class $\mathcal{C}$. More generally, if
$\mathcal{M}$ is a class of graphs such that every graph in $\mathcal{C}$ is
$\mathcal{M}$-induced-minor-free, we refer to graphs in $\mathcal{M}$ as
_forbidden induced minors_ for the class $\mathcal{C}$.

We now consider hereditary graph classes that are closed under edge addition.
We show that for any such class $\mathcal{C}$, both the class $\mathcal{C}$
and the corresponding class $\mathcal{G}_{\mathcal{C}}$ are closed under
induced minors, and we characterize the class $\mathcal{G}_{\mathcal{C}}$ in
terms of forbidden induced minors. For graphs $H_{1}$ and $H_{2}$ on disjoint
vertex sets, the complete join of $H_{1}$ and $H_{2}$, denoted by $H_{1}\vee
H_{2}$, is the graph with vertex set $V(H_{1})\cup V(H_{2})$ and edge set
$E(H_{1})\cup E(H_{2})\cup\\{v_{1}v_{2}\mid v_{1}\in V(H_{1}),v_{2}\in
V(H_{2})\\}$.

######  Theorem 3.1.

Let $\mathcal{C}$ be a hereditary class of graphs, closed under edge addition.
Then both $\mathcal{C}$ and $\mathcal{G}_{\mathcal{C}}$ are closed under
induced minors, and $\mathcal{G}_{\mathcal{C}}$ is precisely the class of all
$\\{2K_{1}\vee H\mid H\in\mathcal{M}_{\mathcal{C}}\\}$-induced-minor-free
graphs.

###### Proof.

Let $\mathcal{C}$ be a hereditary class of graphs, closed under edge addition.
First, we prove that $\mathcal{C}$ is closed under induced minors. It suffices
to show that $\mathcal{C}$ is closed under vertex deletion and edge
contraction. The former follows immediately from the fact that $\mathcal{C}$
is hereditary. Let us prove the latter. Fix a graph $G\in\mathcal{C}$, and fix
an edge $xy\in E(G)$. Then $G/xy$ is isomorphic to the graph obtained from $G$
by first deleting $y$, and then adding edges between $x$ and all vertices in
$N_{G}[y]\setminus N_{G}[x]$; since $\mathcal{C}$ is closed under vertex
deletion and edge addition, it follows that $G/xy$ belongs to $\mathcal{C}$.
So, $\mathcal{C}$ is closed under edge contraction. This proves that
$\mathcal{C}$ is closed under induced minors.

By Corollary 2.2, $\mathcal{G}_{\mathcal{C}}$ is hereditary. So, in order to
prove that $\mathcal{G}_{\mathcal{C}}$ is closed under induced minors, it
suffices to show that $\mathcal{G}_{\mathcal{C}}$ is closed under edge
contractions. Fix $G\in\mathcal{G}_{\mathcal{C}}$, let $xy$ be an edge of $G$,
and set $G^{\prime}:=G/xy$; the vertex of $G^{\prime}$ to which the edge $xy$
is contracted will be denoted by $v^{xy}$. We must show that
$G^{\prime}\in\mathcal{G}_{\mathcal{C}}$, i.e., that for any minimal separator
$S$ of $G^{\prime}$, we have that $G^{\prime}[S]\in\mathcal{C}$.

We first deal with minimal separators of $G^{\prime}$ that contain $v^{xy}$.
So, suppose that $S\subseteq V(G^{\prime})$ is a minimal separator of
$G^{\prime}$ such that $v^{xy}\in S$; we must show that
$G^{\prime}[S]\in\mathcal{C}$. Fix distinct $a,b\in V(G^{\prime})\setminus S$
such that $S$ is a minimal $(a,b)$-separator of $G^{\prime}$. Then
$S^{*}:=(S\setminus\\{v^{xy}\\})\cup\\{x,y\\}$ is an $(a,b)$-separator of $G$.
Let $S^{\prime}\subseteq S^{*}$ be a minimal $(a,b)$-separator of $G$; since
$G\in\mathcal{G}_{\mathcal{C}}$, we have that $G[S^{\prime}]\in\mathcal{C}$.
If $x,y\notin S^{\prime}$, then $S^{\prime}\subsetneqq S$ is an
$(a,b)$-separator of $G^{\prime}$, contrary to the minimality of $S$. So,
$S^{\prime}$ contains at least one of $x,y$. Then
$(S^{\prime}\setminus\\{x,y\\})\cup\\{v^{xy}\\}$ is an $(a,b)$-separator of
$G^{\prime}$; since $(S^{\prime}\setminus\\{x,y\\})\cup\\{v^{xy}\\}\subseteq
S$, the minimality of $S$ implies that
$S=(S^{\prime}\setminus\\{x,y\\})\cup\\{v^{xy}\\}$. As we show next, the graph
$G^{\prime}[S]$ can be obtained from an induced subgraph of $G[S^{\prime}]$ by
possibly adding some edges. By symmetry, we may assume that $x\in S^{\prime}$.
Since $S\setminus\\{v^{xy}\\}=S^{\prime}\setminus\\{x,y\\}$, the graph
$G^{\prime}[S]$ is isomorphic to the graph obtained from the subgraph of
$G[S^{\prime}]$ induced by $S^{\prime}\setminus\\{y\\}$ by adding to it the
edges from $x$ to all vertices in $S^{\prime}\setminus\\{x,y\\}$ that are
adjacent in $G$ to $y$ but not to $x$. Since $G[S^{\prime}]\in\mathcal{C}$,
and $\mathcal{C}$ is hereditary and closed under edge addition, we deduce that
$G^{\prime}[S]\in\mathcal{C}$, and we are done.

We still have to consider minimal separators of $G^{\prime}$ that do not
contain $v^{xy}$. Here, we first observe that for any pair of nonadjacent
vertices $a,b$ of $G^{\prime}$, and any set $S\subseteq
V(G^{\prime})\setminus\\{a,b,v^{xy}\\}=V(G)\setminus\\{a,b,x,y\\}$, both the
following hold:

  * (1)

if $v^{xy}\notin\\{a,b\\}$, then $S$ is an $(a,b)$-separator of $G$ if and
only if $S$ is an $(a,b)$-separator of $G^{\prime}$;

  * (2)

if $v^{xy}=a$, then $S$ is an $(x,b)$-separator of $G$ if and only if $S$ is
an $(a,b)$-separator of $G^{\prime}$.

Clearly, (1) and (2) imply that any set $S\subseteq
V(G^{\prime})\setminus\\{v^{xy}\\}=V(G)\setminus\\{x,y\\}$ is a minimal
separator of $G^{\prime}$ if and only if it is a minimal separator of $G$. But
for any $S\subseteq
V(G^{\prime})\setminus\\{v^{xy}\\}=V(G)\setminus\\{x,y\\}$, we have that
$G^{\prime}[S]=G[S]$, and moreover, if $S$ is a minimal separator of $G$, then
$G[S]\in\mathcal{C}$. This shows that if a set $S\subseteq
V(G^{\prime})\setminus\\{v^{xy}\\}$ is a minimal separator of $G^{\prime}$,
then $G^{\prime}[S]\in\mathcal{C}$.

Finally, it remains to show that $\mathcal{G}_{\mathcal{C}}$ is precisely the
class of all $\\{2K_{1}\vee H\mid H\in\mathcal{M}_{\mathcal{C}}\\}$-induced-
minor-free graphs. Let us first show that all graphs in
$\mathcal{G}_{\mathcal{C}}$ are $\\{2K_{1}\vee H\mid
H\in\mathcal{M}_{\mathcal{C}}\\}$-induced-minor-free. Since
$\mathcal{G}_{\mathcal{C}}$ is closed under induced minors, it suffices to
show that, for all $H\in\mathcal{M}_{\mathcal{C}}$, the graph $2K_{1}\vee H$
does not belong to $\mathcal{G}_{\mathcal{C}}$. So, fix
$H\in\mathcal{M}_{\mathcal{C}}$, and let $x$ and $y$ be the two vertices of
the $2K_{1}$ from $2K_{1}\vee H$. Then $V(H)$ is a minimal $(x,y)$-separator
of $2K_{1}\vee H$. Since the subgraph of $2K_{1}\vee H$ induced by $V(H)$ is
$H$, which does not belong to $\mathcal{C}$ (because
$H\in\mathcal{M}_{\mathcal{C}}$), it follows that $2K_{1}\vee H$ does not
belong to $\mathcal{G}_{\mathcal{C}}$.

For the reverse direction, fix any $\\{2K_{1}\vee H\mid
H\in\mathcal{M}_{\mathcal{C}}\\}$-induced-minor-free graph $G$; we must show
that $G\in\mathcal{G}_{\mathcal{C}}$. Fix distinct, nonadjacent vertices $a$
and $b$ of $G$, and fix a minimal $(a,b)$-separator $S$ of $G$. We must show
that $G[S]\in\mathcal{C}$. Suppose otherwise. Then since $\mathcal{C}$ is
closed under induced minors, there exists some $H\in\mathcal{M}_{\mathcal{C}}$
such that $H$ is an induced minor of $G[S]$. We will derive a contradiction by
showing that $2K_{1}\vee H$ is an induced minor of $G$. Let $\\{X_{v}\\}_{v\in
V(H)}$ be a family of nonempty, pairwise disjoint subsets of $S$, each
inducing a connected subgraph of $G[S]$, and having the property that for all
distinct $u,v\in V(H)$, there is an edge between $X_{u}$ and $X_{v}$ in $G[S]$
if and only if $uv\in E(H)$. Next, let $X_{a}$ (resp., $X_{b}$) be the vertex
set of the component of $G\setminus S$ that contains $a$ (resp., $b$).
Obviously, $X_{a}$ and $X_{b}$ are disjoint and anticomplete to each other in
$G$. Further, since $S$ is a minimal $(a,b)$-separator of $G$, we see that, in
$G$, every vertex of $S$ has a neighbor both in $X_{a}$ and in $X_{b}$. In
particular, for all $v\in V(H)$, there is an edge between $X_{a}$ and $X_{v}$
in $G$, and there is also an edge between $X_{b}$ and $X_{v}$ in $G$. But now
by considering the family $\\{X_{v}\\}_{v\in\\{a,b\\}\cup V(H)}$, we see that
$2K_{1}\vee H$ is an induced minor of $G$ (here, $a$ and $b$ are the two
vertices of the $2K_{1}$). ∎

We now apply Theorem 3.1 to the cases when $\mathcal{C}=\mathcal{C}_{k}$ for
$k\in\\{0,1\\}$, and thus $\mathcal{G}_{\mathcal{C}}=\mathcal{G}_{k}$.

For $k=0$, we have $\mathcal{M}_{\mathcal{C}_{0}}=\\{K_{1}\\}$ and therefore
$\\{2K_{1}\vee H\mid H\in\mathcal{M}_{\mathcal{C}_{0}}\\}=\\{2K_{1}\vee
K_{1}\\}=\\{P_{3}\\}$; we obtain that $\mathcal{G}_{0}$ is precisely the class
of all $P_{3}$-induced-minor-free graphs. In particular, we recover the known
easy fact that the class $\mathcal{G}_{0}$ of all disjoint unions of complete
graphs is precisely the class of all $P_{3}$-induced-minor-free graphs (which
is also the class of all $P_{3}$-free graphs). In this case, since the set of
forbidden induced minors is a singleton, it is in fact also the set of
_minimal_ forbidden induced minors, that is,
$\mathcal{M}_{\mathcal{G}_{0}}=\\{P_{3}\\}$.

For $k=1$, we have $\mathcal{M}_{\mathcal{C}_{1}}=\\{2K_{1}\\}$ and we obtain
that $\\{2K_{1}\vee H\mid H\in\mathcal{M}_{\mathcal{C}_{1}}\\}=\\{2K_{1}\vee
2K_{1}\\}=\\{C_{4}\\}$; that is, $\mathcal{G}_{1}$ is precisely the class of
all $C_{4}$-induced-minor-free graphs. Note that a graph is $C_{4}$-induced-
minor-free if and only if it contains no induced cycles of length greater than
three, that is, it is a chordal graph. By the definition of ${\cal G}_{1}$,
graphs in ${\cal G}_{1}$ are precisely the graphs in which all minimal
separators are cliques. Thus, we have again recovered a known result: a graph
is chordal if and only if all its minimal separators are cliques (see [18]).
Since the set of forbidden induced minors is a singleton, we again conclude
that $\mathcal{M}_{\mathcal{G}_{1}}=\\{C_{4}\\}$.

The reader may wonder whether, in Theorem 3.1, it is necessary to assume that
$\mathcal{C}$ is closed under edge addition. Here, we note that if
$\mathcal{C}$ is the class of all edgeless graphs, then
$K_{2,3}\in\mathcal{G}_{\mathcal{C}}$, but contracting one edge of $K_{2,3}$
produces the diamond, which does not belong to $\mathcal{G}_{\mathcal{C}}$.
Thus, the assumption about edge additions cannot be simply removed from
Theorem 3.1, although it is possible that some other (weaker) assumption would
suffice instead.

######  Corollary 3.2.

For all integers $k\geq 0$, classes $\mathcal{C}_{k}$ and $\mathcal{G}_{k}$
are closed under induced minors, and all graphs in $\mathcal{G}_{k}$ are
$K_{2,k+1}$-induced-minor-free.

###### Proof.

Fix an integer $k\geq 0$. Obviously, $\mathcal{C}_{k}$ is hereditary and
closed under edge addition. So, by Theorem 3.1, $\mathcal{C}_{k}$ is closed
under induced minors, and $\mathcal{G}_{k}=\mathcal{G}_{\mathcal{C}_{k}}$ is
closed under induced minors. It remains to show that
$K_{2,k+1}\notin\mathcal{G}_{k}$. But this is obvious: one minimal separator
of $K_{2,k+1}$ induces an edgeless subgraph on $k+1$ vertices in $K_{2,k+1}$,
and $\mathcal{C}_{k}$ does not contain edgeless graphs on more than $k$
vertices. ∎

We now proceed to showing that when $\mathcal{C}$ is is a hereditary class of
graphs closed not only under edge addition, but also under the addition of
universal vertices, the conclusion of Theorem 3.1 can be strengthened to a
characterization of the class of minimal forbidden induced minors for the
class $\mathcal{G}_{\mathcal{C}}$ (see Theorem 3.6). We start with some
preparatory statements. A nonnull graph is anticonnected if its complement is
connected. An anticomponent of a nonnull graph $G$ is a maximal anticonnected
induced subgraph of $G$. Clearly, every nonnull graph is the complete join of
its anticomponents.

######  Proposition 3.3.

Let $H$ be an anticonnected graph on at least two vertices, and assume that
$H$ is an induced minor of a graph $G$. Let $\\{X_{v}\\}_{v\in V(H)}$ be an
induced minor model of $H$ in $G$. Then there exists an anticomponent $C$ of
$G$ such that $\bigcup_{v\in V(H)}X_{v}\subseteq V(C)$.

###### Proof.

> Claim. For all $v\in V(H)$, there exists an anticomponent $C$ of $G$ such
> that $X_{v}\subseteq V(C)$.

Proof of the Claim. Suppose otherwise. Then there exists some vertex $u\in
V(H)$ and distinct anticomponents $C_{1}$ and $C_{2}$ of $G$ such that $X_{u}$
intersects both $V(C_{1})$ and $V(C_{2})$. Let us show that $u$ is a universal
vertex of $H$. Fix any $w\in V(H)\setminus\\{u\\}$. Let $C$ be any
anticomponent of $G$ such that $X_{w}\cap V(C)\neq\emptyset$. By symmetry, we
may assume that $C\neq C_{1}$.444Indeed, either $C\neq C_{1}$ or $C\neq
C_{2}$, and by symmetry, we may assume that $C\neq C_{1}$. Then $X_{u}\cap
V(C_{1})$ and $X_{w}\cap V(C)$ are both nonempty and complete to each other in
$G$, and in particular, there is at least one edge between $X_{u}$ and $X_{w}$
in $G$. So, $uw\in E(H)$. This proves that $u$ is a universal vertex of $H$.
But this is impossible, since $H$ is an anticonnected graph on at least two
vertices, and consequently, $H$ has no universal vertices. $\blacklozenge$

Fix any anticomponent $C$ of $G$ such that $\Big{(}\bigcup_{v\in
V(H)}X_{v}\Big{)}\cap V(C)\neq\emptyset$, and set $U:=\\{v\in V(H)\mid
X_{v}\cap V(C)\neq\emptyset\\}$. By construction, we have that
$U\neq\emptyset$, and by the claim, we have that $U=\\{v\in V(H)\mid
X_{v}\subseteq V(C)\\}$. It now suffices to show that $U=V(H)$, for it will
then follow that $\bigcup_{v\in V(H)}X_{v}\subseteq V(C)$, which is what we
need. Since $U\neq\emptyset$ and $H$ is anticonnected, it is in fact enough to
show that $U$ is complete to $V(H)\setminus U$ in $H$. So, fix some $u\in U$
and $w\in V(H)\setminus U$. Since $u\in U$, we have that $X_{u}\subseteq
V(C)$. On the other hand, by the claim, there exists an anticomponent $D$ of
$G$ such that $X_{w}\subseteq V(D)$; since $w\notin U$, we have that $D\neq
C$. Since $C$ and $D$ are distinct anticomponents of $G$, we know that $V(C)$
and $V(D)$ are complete to each other in $G$; consequently, $X_{u}$ is
complete to $X_{w}$ in $G$, and it follows that $uw\in E(H)$. This proves that
$U$ is complete to $V(H)\setminus U$, and we are done. ∎

######  Proposition 3.4.

Let $H_{1}$ and $H_{2}$ be graphs. Assume that $H_{1}$ contains no universal
vertices and that $2K_{1}\vee H_{1}$ is an induced minor of $2K_{1}\vee
H_{2}$. Then $H_{1}$ is an induced minor of $H_{2}$.

###### Proof.

If $H_{1}$ is the null graph, then it is obviously an induced minor of
$H_{2}$. So, we may assume that $H_{1}$ is nonnull. Since $2K_{1}\vee H_{1}$
is an induced minor of $2K_{1}\vee H_{2}$, it follows that the graph $H_{2}$
is also nonnull.

Now, using the fact that $2K_{1}\vee H_{1}$ is an induced minor of $2K_{1}\vee
H_{2}$, we fix an induced minor model $\\{X_{v}\\}_{v\in V(2K_{1}\vee H_{1})}$
of $2K_{1}\vee H_{1}$ in $2K_{1}\vee H_{2}$. If $\bigcup_{v\in
V(H_{1})}X_{v}\subseteq V(H_{2})$, then $H_{1}$ is an induced minor of
$H_{2}$, and we are done. So, we may assume that $\bigcup_{v\in
V(H_{1})}X_{v}\not\subseteq V(H_{2})$. Fix an anticomponent $H$ of $H_{1}$
such that $\bigcup_{v\in V(H)}X_{v}\not\subseteq V(H_{2})$. Since $H_{1}$ has
no universal vertices, we have that $|V(H)|\geq 2$. In view of Proposition
3.3, it follows that $\bigcup_{v\in V(H)}X_{v}\subseteq V(2K_{1})$. Since $H$
has at least two vertices, it follows that $H\cong 2K_{1}$ and $\bigcup_{v\in
V(H)}X_{v}=V(2K_{1})$. Consequently, $\bigcup_{v\in V(2K_{1}\vee
H_{1})\setminus V(H)}X_{v}\subseteq V(H_{2})$, and see that $(2K_{1}\vee
H_{1})\setminus V(H)$ is an induced minor of $H_{2}$. But note that
$(2K_{1}\vee H_{1})\setminus V(H)\cong H_{1}$. So, $H_{1}$ is an induced minor
of $H_{2}$. ∎

We note that the assumption that $H_{1}$ contains no universal vertices cannot
be removed from Proposition 3.4. To see this, note that $2K_{1}\vee K_{2}$ is
an induced minor of $2K_{1}\vee 3K_{1}$ (indeed, we obtain $2K_{1}\vee K_{2}$
by contracting any one edge of $2K_{1}\vee 3K_{1}$), but $K_{2}$ is not an
induced minor of $3K_{1}$.

######  Lemma 3.5.

Let $\mathcal{C}$ be a class of graphs, closed under the addition of universal
vertices. Then no graph in $\mathcal{M}_{\mathcal{C}}$ contains a universal
vertex. Moreover, for any two nonisomorphic graphs
$H_{1},H_{2}\in\mathcal{M}_{\mathcal{C}}$, the graphs $2K_{1}\vee H_{1}$ and
$2K_{1}\vee H_{2}$ are incomparable with respect to the induced minor
relation.

###### Proof.

Let us first show that no graph in $\mathcal{M}_{\mathcal{C}}$ contains a
universal vertex. Suppose otherwise, and fix a graph
$H\in\mathcal{M}_{\mathcal{C}}$ that contains a universal vertex $u$. By the
definition of $\mathcal{M}_{\mathcal{C}}$, we have that $H\setminus u$ belongs
to $\mathcal{C}$. But then since $\mathcal{C}$ is closed under the addition of
universal vertices, we have that $H\in\mathcal{C}$, contrary to the fact that
$H\in\mathcal{M}_{\mathcal{C}}$.

Now, fix any two nonisomorphic graphs
$H_{1},H_{2}\in\mathcal{M}_{\mathcal{C}}$. By the definition of
$\mathcal{M}_{\mathcal{C}}$, the graphs $H_{1}$ and $H_{2}$ are incomparable
with respect to the induced minor relation. Moreover, by what we just proved,
$H_{1}$ and $H_{2}$ have no universal vertices. So, by Proposition 3.4,
$2K_{1}\vee H_{1}$ and $2K_{1}\vee H_{2}$ are incomparable with respect to the
induced minor relation. ∎

######  Theorem 3.6.

Let $\mathcal{C}$ be a hereditary class of graphs, closed under edge addition,
and closed under the addition of universal vertices. Then
$\mathcal{M}_{\mathcal{G}_{\mathcal{C}}}=\\{2K_{1}\vee H\mid
H\in\mathcal{M}_{\mathcal{C}}\\}$.

###### Proof.

By Theorem 3.1, $\mathcal{G}_{\mathcal{C}}$ is precisely the class of all
$\\{2K_{1}\vee H\mid H\in\mathcal{M}_{\mathcal{C}}\\}$-induced-minor-free
graphs. On the other hand, Lemma 3.5 guarantees that nonisomorphic graphs in
$\\{2K_{1}\vee H\mid H\in\mathcal{M}_{\mathcal{C}}\\}$ are incomparable with
respect to the induced minor relation. So,
$\mathcal{M}_{\mathcal{G}_{\mathcal{C}}}=\\{2K_{1}\vee H\mid
H\in\mathcal{M}_{\mathcal{C}}\\}$. ∎

We now apply Theorem 3.6 to the cases when $\mathcal{C}=\mathcal{C}_{2}$, and
thus $\mathcal{G}_{\mathcal{C}}=\mathcal{G}_{2}$. It can be shown that
$\mathcal{M}_{\mathcal{G}_{2}}=\\{\overline{K_{2}\cup C_{2k+1}}\mid
k\in\mathbb{N}\\}$ (see Fig. 1). To this end, the following auxiliary
proposition will be useful.

Figure 1: Some small graphs in $\mathcal{M}_{\mathcal{G}_{2}}$.

######  Proposition 3.7.

If a graph $H_{1}$ is an induced minor of a graph $H_{2}$, then
$\overline{H_{1}}$ is isomorphic to a (not necessarily induced) subgraph of
$\overline{H_{2}}$.

###### Proof.

The result follows from the following technical claim via simple induction.

> Claim. If a graph $H$ is obtained from a graph $G$ by deleting one vertex or
> contracting one edge, then $\overline{H}$ is isomorphic to a subgraph of
> $\overline{G}$.

Proof of the Claim. Fix graphs $H$ and $G$, and assume that $H$ is obtained
from $G$ by deleting one vertex or contracting one edge. We must show that
$\overline{H}$ is isomorphic to a (not necessarily induced) subgraph of
$\overline{G}$. If $H$ is obtained from $G$ by deleting one vertex, then this
is obvious. So, assume that $H$ is obtained from $G$ by contracting an edge
$xy$ of $G$. Then $\overline{H}$ is isomorphic to the graph obtained from
$\overline{G}$ by first deleting $y$ and then deleting all edges between $x$
and $N_{G}[y]\setminus N_{G}[x]=N_{\overline{G}}(x)\setminus
N_{\overline{G}}(y)$. So, $\overline{H}$ is isomorphic to a subgraph of
$\overline{G}$. $\blacklozenge$ ∎

######  Corollary 3.8.

$\mathcal{M}_{\mathcal{G}_{2}}=\\{\overline{K_{2}\cup C_{2k+1}}\mid
k\in\mathbb{N}\\}$.

###### Proof.

Note that for all positive integers $k$, we have that $\overline{K_{2}\cup
C_{2k+1}}\cong 2K_{1}\vee\overline{C_{2k+1}}$. So, in view of Theorem 3.6, it
is enough to show that
$\mathcal{M}_{\mathcal{C}_{2}}=\\{\overline{C_{2k+1}}\mid k\in\mathbb{N}\\}$.
Note that graphs in $\mathcal{C}_{2}$ are precisely the complements of
bipartite graphs, and it is well known that a graph is bipartite if and only
if it contains no odd cycle as an induced subgraph. So, $\mathcal{C}_{2}$ is
precisely the class of all $\\{\overline{C_{2k+1}}\mid k\in\mathbb{N}\\}$-free
graphs. Since $\mathcal{C}_{2}$ is closed under induced minors (by Corollary
3.2), it follows that $\mathcal{C}_{2}$ is in fact the class of all
$\\{\overline{C_{2k+1}}\mid k\in\mathbb{N}\\}$-induced-minor-free graphs. It
remains to show that (nonisomorphic) graphs in $\\{\overline{C_{2k+1}}\mid
k\in\mathbb{N}\\}$ are incomparable with respect to the induced minor
relation. But this follows from Proposition 3.7, and from the fact that no
cycle is a subgraph of a cycle of different length. ∎

A graph is _$1$ -perfectly-orientable_ if it admits an orientation in which
the out-neighborhood of each vertex is a clique of the underlying graph. It
was shown by Hartinger and Milanič in [22] that all $1$-perfectly-orientable
graphs are $\\{\overline{K_{2}\cup C_{2k+1}}\mid k\in\mathbb{N}\\}$-induced-
minor-free. Thus, Corollary 3.8 implies that $1$-perfectly-orientable graphs
form a subclass of $\mathcal{G}_{2}$. Let us also remark that the proof of the
mentioned result in [22] also gives a proof of the fact that nonisomorphic
graphs in $\\{\overline{K_{2}\cup C_{2k+1}}\mid k\in\mathbb{N}\\}$ are
incomparable with respect to the induced minor relation, which, when combined
with Theorem 3.6, gives an alternative proof of Corollary 3.8.

###  3.1 Algorithmic considerations

It was shown by Dallard et al. in [15] that, for each positive integer $k$,
the Maximum Weight Stable Set problem can be solved in $\mathcal{O}(n^{2k})$
time for $n$-vertex $K_{2,k}$-induced-minor-free graphs. To connect this
result with the classes $\mathcal{G}_{k}$, by Corollary 3.2 every graph in
$\mathcal{G}_{k}$ is $K_{2,k+1}$-induced-minor-free. Therefore, the result by
Dallard et al. implies the following.

######  Corollary 3.9.

For each integer $k\geq 0$, the Maximum Weight Stable Set problem can be
solved in $\mathcal{O}(n^{2k+2})$ time for $n$-vertex graphs in
$\mathcal{G}_{k}$.

Similar results hold for a number of other related problems, including the
Maximum Induced Matching problem, the Dissociation Set problem, etc. We refer
to [17] for the details.

Furthermore, Dallard et al. showed in [16] that in any class of
$K_{2,k}$-induced-minor-free graphs, the treewidth of the graphs in the class
is bounded from above by some polynomial function of the clique number (see
also [15]). Combining this with a result of Chaplick et al. [11, Theorem 12],
it follows that for any two positive integers $k$ and $\ell$, the
$\ell$-Coloring problem is solvable in time $\mathcal{O}(n)$ in the class of
$n$-vertex $K_{2,k}$-induced-minor-free graphs, and thus in the class
$\mathcal{G}_{k}$ as well. (The $\mathcal{O}$-notation hides a constant
depending on $k$ and $\ell$.) The same result holds in fact for the more
general List $\ell$-Coloring problem, in which every vertex is equipped with a
list of available colors from the set $\\{1,\ldots,\ell\\}$.

##  4 Vertex neighborhoods

Recall that a vertex $v$ in a graph $G$ is _$k$ -simplicial_ it its
neighborhood is a union of $k$ cliques. Given a graph $G$ and an integer
$k\geq 0$, a _$k$ -simplicial elimination ordering_ of $G$ is an ordering
$v_{1},\dots,v_{n}$ of the vertices of $G$ such that for all
$i\in\\{1,\dots,n\\}$, $v_{i}$ is $k$-simplicial in the graph
$G[v_{1},\dots,v_{i}]$ For $k=1$, resp. $k=2$, a $k$-simplicial elimination
ordering is also called a _perfect elimination ordering_ , resp. a
_bisimplicial elimination ordering_.

A classical result due to Dirac [18] states that every nonnull chordal graph
has a simplicial vertex. An alternative proof of this result was given by
Rose, Tarjan, and Lueker [27], who showed that every LexBFS ordering of a
chordal graph is a perfect elimination ordering. In this section we generalize
these results by showing that for every positive integer $k$, every LexBFS
ordering of a graph in $\mathcal{G}_{k}$ is a $k$-simplicial elimination
ordering. In particular, this shows that every nonnull graph in
$\mathcal{G}_{k}$ has a $k$-simplicial vertex. We also examine some
algorithmic consequences of these results for the case $k=2$.

For a family $\mathcal{F}$ of graphs, an ordering $v_{1},\ldots,v_{n}$ of the
vertices of a graph $G$ is an _${\cal F}$ -elimination ordering_ if for every
index $i\in\\{1,\ldots,n\\}$, the graph $G[N_{G[v_{1},\ldots,v_{i}]}(v_{i})]$
is ${\cal F}$-free. Note that a graph $G$ admits an ${\cal F}$-elimination
ordering if and only if every nonnull induced subgraph of $G$ contains a
vertex whose neighborhood induces an ${\cal F}$-free subgraph in $G$.

LexBFS is a linear-time algorithm of Rose, Tarjan, and Lueker [27] whose input
is any nonnull graph $G$ together with a vertex $s\in V(G)$, and whose output
is an ordering of the vertices of $G$ starting at $s$. It is a restricted
version of Breadth First Search, where the usual queue of vertices is replaced
by a queue of unordered subsets of the vertices, which is sometimes refined,
but never reordered (for details, see [27]). An ordering of the vertices of a
graph $G$ is a _LexBFS ordering_ if there exists a vertex $s$ of $G$ such that
the ordering can be produced by LexBFS when the input is $G,s$.

In certain cases, ${\cal F}$-elimination orderings can be found using LexBFS.
This relies on the concept of locally ${\cal F}$-decomposable graphs and graph
classes, introduced by Aboulker et al. in [1]. Let ${\cal F}$ be a family of
graphs. A graph $G$ is _locally ${\cal F}$-decomposable_ if for every vertex
$v$ of $G$, every $F\in{\cal F}$ contained, as an induced subgraph, in
$G[N_{G}(v)]$ and every component $C$ of $G\setminus N_{G}[v]$, there exists
$y\in V(F)$ such that $y$ has a nonneighbor in $F$ and has no neighbors in
$C$. A class of graphs ${\cal G}$ is _locally ${\cal F}$-decomposable_ if
every graph $G\in{\cal G}$ is a locally ${\cal F}$-decomposable graph.

######  Theorem 4.1 (Aboulker et al. [1]).

If ${\cal F}$ is a family of noncomplete graphs and $G$ is a locally ${\cal
F}$-decomposable graph, then every LexBFS ordering of $G$ is an ${\cal
F}$-elimination ordering.

For a hereditary graph class $\mathcal{C}$, we denote by
$\mathcal{F}_{\mathcal{C}}$ the class of all graphs $G$ such that $G$ does not
belong to $\mathcal{C}$, but all proper induced subgraphs of $G$ do belong to
$\mathcal{C}$.

######  Theorem 4.2.

Let $\mathcal{C}$ be a hereditary class of graphs that is closed under the
addition of universal vertices. Then, for every graph
$G\in\mathcal{G}_{\mathcal{C}}$, every LexBFS ordering of $G$ is an
$\mathcal{F}_{\mathcal{C}}$-elimination ordering.

###### Proof.

First, we note that no graph in $\mathcal{F}_{\mathcal{C}}$ contains a
universal vertex (and thus, $\mathcal{F}_{\mathcal{C}}$ is a family of
noncomplete graphs). Indeed, if some $F\in\mathcal{F}_{\mathcal{C}}$ contained
a universal vertex $u$, then the definition of $\mathcal{F}_{\mathcal{C}}$
would imply that $F\setminus u$ belongs to $\mathcal{C}$, and since
$\mathcal{C}$ is closed under the addition of universal vertices, it would
follow that $F\in{\mathcal{C}}$, a contradiction.

Now, fix a graph $G\in\mathcal{G}_{\mathcal{C}}$. We claim that $G$ is locally
$\mathcal{F}_{\mathcal{C}}$-decomposable. Consider a vertex $x\in V(G)$.
Suppose that $F$ is an induced subgraph of $G[N_{G}(x)]$ such that
$F\in\mathcal{F}_{\mathcal{C}}$. By the above, $F$ does not contain a
universal vertex, and consequently, every vertex of $F$ has a nonneighbor in
$F$. Let $C$ be a component of $G\setminus N_{G}[x]$; we must show that some
vertex in $F$ is anticomplete to $V(C)$. Suppose otherwise, that is, suppose
that every vertex in $V(F)$ has a neighbor in $V(C)$. Let $z\in V(C)$.
Clearly, $N_{G}(x)$ is an $(x,z)$-separator of $G$, and moreover, any minimal
$(x,z)$-separator of $G$ included in $N_{G}(x)$ includes $V(F)$; since
$G\in\mathcal{G}_{\mathcal{C}}$ and $\mathcal{C}$ is hereditary, it follows
that $F\in\mathcal{C}$, contrary to the fact that
$F\in\mathcal{F}_{\mathcal{C}}$. Thus, some vertex in $V(F)$ is indeed
anticomplete to $V(C)$. It follows that $G$ is locally
$\mathcal{F}_{\mathcal{C}}$-decomposable, and so by Theorem 4.1, every LexBFS
ordering of $G$ is an $\mathcal{F}_{\mathcal{C}}$-elimination ordering. This
completes the proof. ∎

The reader may wonder whether, in Theorem 4.2, it might be possible to
eliminate the hypothesis that $\mathcal{C}$ is closed under the addition of
universal vertices. This would in fact not be possible (at least not without
adding some other, perhaps weaker, hypothesis). To see this, fix any positive
integer $\ell$, and any hereditary class $\mathcal{C}$ that does not contain
$K_{\ell}$. The class $\mathcal{G}_{\mathcal{C}}$ contains all complete
graphs, and in particular, $K_{\ell+1}\in\mathcal{G}_{\mathcal{C}}$. However,
the neighborhood of any vertex of $K_{\ell+1}$ induces a $K_{\ell}$, and
$K_{\ell}\notin\mathcal{C}$.

######  Corollary 4.3.

Let $k$ be a positive integer. Then, for every graph $G$ in $\mathcal{G}_{k}$,
every LexBFS ordering of $G$ is a $k$-simplicial elimination ordering.

###### Proof.

Fix an integer $k\geq 1$. Recall that $\mathcal{C}_{k}$ is the class of graphs
whose vertex set can be partitioned into $k$ cliques. Let
$G\in\mathcal{C}_{k}$, and let $C_{1},\ldots,C_{k}$ be $k$ cliques in $G$
partitioning the vertex set of $G$. If $G^{\prime}$ is the graph obtained by
adding a universal vertex $u$ to $G$, then
$C_{1}\cup\\{u\\},C_{2},\ldots,C_{k}$ are $k$ cliques in $G^{\prime}$ forming
a partition of the vertex set of $G^{\prime}$. It follows that
$\mathcal{C}_{k}$ is closed under the addition of universal vertices. By
Theorem 4.2, for every graph $G$ in $\mathcal{G}_{k}$, every LexBFS ordering
of $G$ is a $k$-simplicial elimination ordering. ∎

######  Corollary 4.4.

For every positive integer $k$, every nonnull graph in $\mathcal{G}_{k}$ has a
$k$-simplicial vertex.

######  Remark 4.5.

Corollary 4.3 can also be obtained from the fact that every nonnull graph $G$
contains a _moplex_ [6], that is, a clique $C$ such that every two vertices in
$C$ have the same closed neighborhood and the neighborhood of $C$ is either
empty or a minimal separator of $G$. (In fact, the last vertex visited by any
execution of LexBFS on $G$ necessarily belongs to a moplex.) Given a graph
$G\in\mathcal{G}_{k}$ and a vertex $v$ that belongs to a moplex $C$ of $G$,
there exist $k$ cliques $C_{1},\ldots,C_{k}$ covering the neighborhood of $C$.
But then $C_{1},\ldots,C_{k}\cup(C\setminus\\{v\\})$ are $k$ cliques covering
$N_{G}(v)$, showing that $v$ is a $k$-simplicial vertex.

######  Remark 4.6.

For $k>1$, the statement of Corollary 4.3 does not generalize to the class of
graphs that admit a $k$-simplicial elimination ordering. To see this, let $G$
be the complete bipartite graph $K_{2,k+1}$. Then, $G$ admits a bisimplicial
elimination ordering obtained by placing the two vertices of degree $k+1$
before all the $k+1$ the vertices of degree $2$ in the ordering. On the other
hand, any LexBFS ordering of $G$ starting at a vertex with degree $k+1$ will
end in the other vertex of degree $k+1$, which is not a $k$-simplicial vertex
in $G$.

###  4.1 Algorithmic implications

The Maximum Weight Clique problem can be solved in polynomial time for
$n$-vertex graphs that admit a bisimplicial elimination ordering, see [30].
The algorithm iteratively removes bisimplicial vertices and reduces the
problem to solving $n$ instances of the Maximum Weight Stable Set problem in
bipartite graphs. The polynomial running time of the algorithm given in [30]
was based on polynomial-time solvability of the Maximum Weight Stable Set
problem in the class of perfect graphs. Using maximum flow techniques, an
improved running time of $\mathcal{O}(n^{4})$ can be achieved, see [5]. For
graphs in $\mathcal{G}_{2}$, a further improvement can be obtained using
LexBFS and recent developments on maximum flow algorithms.

######  Theorem 4.7.

For every $\epsilon>0$, the Maximum Weight Clique problem can be solved in
$\mathcal{O}(n^{3+\epsilon})$ time for $n$-vertex graphs in $\mathcal{G}_{2}$.

###### Proof.

Let $G$ be an $n$-vertex graph in $\mathcal{G}_{2}$. In time
$\mathcal{O}(n^{2})$, we compute a LexBFS ordering $v_{1},\ldots,v_{n}$ of
$G$. By Corollary 4.3, $v_{1},\ldots,v_{n}$ is a bisimplicial elimination
ordering of $G$. For each $i\in\\{1,\ldots,n\\}$, let $G_{i}$ be the graph
induced by the closed neighborhood of $v_{i}$ in the graph
$G[v_{1},\dots,v_{i}]$. We will show that for each $i\in\\{1,\ldots,n\\}$, we
can compute a maximum-weight clique $C_{i}$ in $G_{i}$ in time
$\mathcal{O}(n^{2+\epsilon})$. This will suffice, since a clique $C_{i}$ with
maximum total weight is also a clique in $G$ with maximum total weight.

Fix an $i\in\\{1,\ldots,n\\}$. A maximum-weight clique in the graph $G_{i}$
consists of $v_{i}$ and a maximum-weight stable set in the complement of the
graph $G_{i}-v_{i}$. Since $v_{i}$ is a bisimplicial vertex in the graph
$G[v_{1},\dots,v_{i}]$, the complement of the graph $G_{i}-v_{i}$ is
bipartite. The problem of finding a maximum-weight stable set in a vertex-
weighted bipartite graph can be reduced in linear time to a maximum flow
problem in a derived network (see, e.g., [19]). Using a recent result due to
Chen et al. [12] showing that the maximum flow problem can be solved in almost
linear time, we conclude that a maximum-weight independent set in the
complement of the graph $G_{i}-v_{i}$ can be computed in time
$\mathcal{O}(n^{2+\epsilon}).$ The claimed $\mathcal{O}(n^{3+\epsilon})$
overall time complexity follows. ∎

As we will show in the next section (more specifically in LABEL:thm-max-
clique-\NP-hard), this result cannot be generalized to graphs in
$\mathcal{G}_{k}$ for $k\geq 3$, unless P = NP.

##  5 NP-hardness results for $\mathcal{G}_{k}$, $k\geq 3$

In this section we prove that for all $k\geq 3$, it is NP-hard to recognize
graphs in $\mathcal{G}_{k}$. The time complexity of recognizing graphs in
$\mathcal{G}_{2}$ is still unknown. We also show that the Maximum Clique
problem is NP-hard for $\mathcal{G}_{3}$ (and consequently for
$\mathcal{G}_{k}$ whenever $k\geq 3$).

Recall that for an integer $k$, the $k$-Coloring problem is the problem of
determining whether the input graph is $k$-colorable. It is well known that
for any integer $k\geq 3$, the $k$-Coloring problem is NP-complete; we prove
the NP-hardness of recognizing graphs in $\mathcal{G}_{k}$ ($k\geq 3$) by a
reduction from this problem. We begin with a technical proposition.

######  Proposition 5.1.

Let $k\geq 0$ be an integer, and let $G$ be a graph. Let $G^{\prime}$ be the
graph obtained from $G$ by adding two new, nonadjacent vertices, and making
them adjacent to all vertices of $G$. Then $\chi(\overline{G})\leq k$ if and
only if $G^{\prime}\in\mathcal{G}_{k}$.

###### Proof.

Let $a$ and $b$ be the two vertices added to $G$ to form $G^{\prime}$.

Suppose first that $G^{\prime}\in\mathcal{G}_{k}$. Clearly, $V(G)$ is a
minimal $(a,b)$-separator of $G^{\prime}$, and so $V(G)$ is a union of $k$
cliques of $G^{\prime}$. But then $\chi(\overline{G})\leq k$.

Suppose now that $\chi(\overline{G})\leq k$; we must show that
$G^{\prime}\in\mathcal{G}_{k}$. Fix two distinct, nonadjacent vertices $x,y\in
V(G^{\prime})$ and let $S$ be a minimal $(x,y)$-separator of $G^{\prime}$. We
must show that $S$ is a union of $k$ cliques of $G^{\prime}$.

Suppose first that $\\{x,y\\}\cap\\{a,b\\}\neq\emptyset$. By symmetry, we may
assume that $x=a$. Since $b$ is the only nonneighbor of $a$ in $G^{\prime}$,
it follows that $y=b$. Since $\\{a,b\\}=\\{x,y\\}$ is complete to
$V(G)=V(G^{\prime})\setminus\\{a,b\\}$, it follows that $V(G)$ is the only
$(x,y)$-separator of $G^{\prime}$. So, $S=V(G)$. Since $\chi(\overline{G})\leq
k$, it follows that $S$ is a union of $k$ cliques of $G^{\prime}$.

From now on, we assume that $\\{x,y\\}\cap\\{a,b\\}=\emptyset$, so that
$x,y\in V(G)$. Since $x$ and $y$ are nonadjacent, we see that $V(G)$ is not a
clique, and consequently $k\geq\chi(\overline{G})\geq 2$. Note that
$\\{a,b\\}$ is complete to $\\{x,y\\}$, and so $a,b\in S$. Now,
$\chi(\overline{G})\leq k$, and so $S\setminus\\{a,b\\}$ is a union of $k$
cliques of $G$, say $C_{1},\dots,C_{k}$. Using the fact that $\\{a,b\\}$ is
complete to $V(G)$ in $G^{\prime}$, and the fact that $k\geq 2$, we see that
$S$ is a union of $k$ cliques of $G^{\prime}$, namely
$C_{1}\cup\\{a\\},C_{2}\cup\\{b\\},C_{3},\dots,C_{k}$.

We have now shown that $G^{\prime}\in\mathcal{G}_{k}$, and we are done. ∎

######  Theorem 5.2.

For every integer $k\geq 3$, it is NP-hard to recognize graphs in
$\mathcal{G}_{k}$.

###### Proof.

Fix an integer $k\geq 3$, and let $G$ be any graph. We form a graph
$G^{\prime}$ by adding two new, nonadjacent vertices to $\overline{G}$, and
making them adjacent to all vertices of $\overline{G}$. Since
$\overline{\overline{G}}=G$, Proposition 5.1 guarantees that $\chi(G)\leq k$
if and only if $G^{\prime}\in\mathcal{G}_{k}$. Since $k$-Coloring is NP-
complete, it follows that recognizing graphs in $\mathcal{G}_{k}$ is NP-hard.
∎

######  Theorem 5.3.

The Maximum Clique problem is NP-hard for graphs in $\mathcal{G}_{3}$.

###### Proof.

Note that $\mathcal{G}_{3}$ contains all graphs whose vertex set can be
partitioned into three cliques; moreover, note that the vertex set of a graph
can be partitioned into three cliques if and only if the complement of the
graph is $3$-colorable. Thus, it suffices to show that the Maximum Stable Set
problem is NP-hard for 3-colorable graphs. But this readily follows from [26].
Indeed, as observed by Poljak [26], for any graph $G$, the graph $G^{*}$
obtained from $G$ by subdividing each edge twice has the property that
$\alpha(G^{*})=\alpha(G)+|E(G)|$. But notice that for any graph $G$, the graph
$G^{*}$ is 3-colorable. Thus, since the Maximum Stable Set problem is NP-hard
for general graphs, it is NP-hard for 3-colorable graphs. ∎

##  6 Diamond-free graphs in $\mathcal{G}_{2}$

We remind the reader that the _diamond_ is the four-vertex graph obtained from
the complete graph $K_{4}$ by deleting one edge (see Fig. 2). In this section,
we prove a decomposition theorem for diamond-free graphs in $\mathcal{G}_{2}$,
which implies a polynomial-time recognition algorithm for this class of
graphs. We begin with some definitions.

Figure 2: The diamond. Figure 3: Some small wheels, classified as broken or
not broken. Figure 4: Three-path-configurations: theta (left), pyramid
(center), and prism (right). A full line represents an edge, and a dashed line
represents a path that has at least one edge.

A _hole_ in a graph $G$ is an induced cycle of $G$ of length at least four. A
_wheel_ is a graph that consists of a hole and an additional vertex that has
at least three neighbors in the hole. A _broken wheel_ (see Fig. 3) is a wheel
that consists of a hole $H$ and an additional vertex $v$ such that $v$ has at
least three neighbors in $H$, and furthermore, the neighbors of $v$ in $V(H)$
induce a disconnected subgraph of $H$.

A _prism_ is any subdivision of $\overline{C_{6}}$ in which the two triangles
remain unsubdivided; in particular, $\overline{C_{6}}$ is a prism. A _pyramid_
is any subdivision of the complete graph $K_{4}$ in which one triangle remains
unsubdivided, and of the remaining three edges, at least two edges are
subdivided at least once. A _theta_ is any subdivision of the complete
bipartite graph $K_{2,3}$; in particular, $K_{2,3}$ is a theta. A _3-path-
configuration_ (or _3PC_ for short) is any theta, pyramid, or prism. The three
types of 3PC are represented in Fig. 4.

The _short prism_ is the graph $\overline{C_{6}}$, and a _long prism_ is any
prism other than $\overline{C_{6}}$. (Thus, a long prism is any prism on at
least seven vertices.)

For an integer $n\geq 3$, a _short $n$-prism_ is a graph whose vertex set can
be partitioned into two $n$-vertex cliques, say $A=\\{a_{1},\dots,a_{n}\\}$
and $B=\\{b_{1},\dots,b_{n}\\}$, such that for all $i,j\in\\{1,\dots,n\\}$,
$a_{i}$ is adjacent to $b_{j}$ if and only if $i=j$. Note that
$\overline{C_{6}}$ is a short $3$-prism, while for $n\geq 4$, no short
$n$-prism is a prism. A _complete prism_ is any graph that is a short
$n$-prism for some integer $n\geq 3$.

We will need the following decomposition theorem for (3PC, wheel)-free graphs.

######  Theorem 6.1 (Conforti et al. [13]).

If a graph $G$ is (3PC, wheel)-free, then either $G$ is a complete graph or a
cycle, or $G$ admits a clique-cutset.

######  Lemma 6.2.

$K_{2,3}$ is an induced minor of every theta, pyramid, long prism, or broken
wheel.

###### Proof.

First, we show that $K_{2,3}$ is an induced minor of every theta. Let $H$ be a
theta. Let $a$ and $b$ be distinct, nonadjacent vertices of $H$, and let
$P^{1},P^{2},P^{3}$ be distinct induced paths in $H$, each between $a$ and
$b$, such that any two of $P^{1},P^{2},P^{3}$ have exactly two vertices
(namely $a$ and $b$) in common. Contracting in $H$ all but two edges of each
path $P^{i}$ results in a graph isomorphic to $K_{2,3}$.

Next, we show that $K_{2,3}$ is an induced minor of every pyramid. Let $H$ be
a pyramid. Let $a$ be a vertex of $H$, let $B=\\{b_{1},b_{2},b_{3}\\}$ be a
3-vertex clique in $H\setminus a$, and let $P^{1}$, $P^{2}$, and $P^{3}$ be
induced paths in $H$ such that

  * •

for each $i\in\\{1,2,3\\}$, the endpoints of $P^{i}$ are $a$ and $b_{i}$;

  * •

any two of the paths $P^{1},P^{2},P^{3}$ have exactly one vertex (namely $a$)
in common.

Since $H$ is a pyramid, we know that at least two of $P^{1},P^{2},P^{3}$ have
more than one edge; by symmetry, we may assume that $P^{1}$ and $P^{2}$ each
have at least two edges. Contracting in $H$ all but two edges of each of the
paths $P^{1}$ and $P^{2}$, all but one edge of the path $P^{3}$, and the edge
$b_{1}b_{2}$ results in a graph isomorphic to $K_{2,3}$.

Next, we show that $K_{2,3}$ is an induced minor of every long prism. Let $H$
be a long prism. Let $A=\\{a_{1},a_{2},a_{3}\\}$ and
$B=\\{b_{1},b_{2},b_{3}\\}$ be disjoint 3-vertex cliques in $H$, and let
$P^{1}$, $P^{2}$, and $P^{3}$ be induced paths in $H$ such that

  * •

for each $i\in\\{1,2,3\\}$, the endpoints of $P^{i}$ are $a_{i}$ and $b_{i}$;

  * •

no two of the paths $P^{1},P^{2},P^{3}$ have any vertices in common.

Since $H$ is a long prism, we know that at least one of $P^{1},P^{2},P^{3}$
has more than one edge; by symmetry, we may assume that $P^{1}$ has more than
one edge. Contracting in $H$ all but two edges of the path $P^{1}$, all but
one edges of each of the paths $P^{2}$ ad $P^{3}$, and the edges $a_{1}a_{2}$
and $b_{1}b_{3}$ results in a graph isomorphic to $K_{2,3}$.

Finally, we show that $K_{2,3}$ is an induced minor of every broken wheel. Let
$W$ be a broken wheel, consisting of a hole
$H=h_{0},h_{1},\dots,h_{k-1},h_{0}$ (with $k\geq 4$, and indices in
$\mathbb{Z}_{k}$) and an additional vertex $v$ that has at least three
neighbors in $H$, and such that the neighbors of $v$ induce a disconnected
subgraph of $H$. By symmetry, we may assume that $v$ is nonadjacent to $h_{0}$
and adjacent to $h_{1}$. Let the path $h_{1},\dots,h_{i}$ be one component of
$H[N_{W}(v)]$. Contracting in $W$ all edges of the hole $H$ except for the
four edges $h_{0}h_{1},h_{0}h_{k-1},h_{i}h_{i+1},h_{i+1}h_{i+2}$ results in a
graph isomorphic to $K_{2,3}.$ ∎

######  Corollary 6.3.

Every graph in $\mathcal{G}_{2}$ is (theta, pyramid, long prism, broken
wheel)-free.

###### Proof.

Since $\mathcal{G}_{2}$ is hereditary (by Corollary 2.2), it suffices to show
that $\mathcal{G}_{2}$ contains no theta, no pyramid, no long prism, and no
broken wheel. By Corollary 3.2, $\mathcal{G}_{2}$ is a subclass of the class
of $K_{2,3}$-induced-minor-free graphs. Thus, it suffices to show that the
class of $K_{2,3}$-induced-minor-free graphs contains no theta, no pyramid, no
long prism, and no broken wheel, or equivalently, that $K_{2,3}$ is an induced
minor of every theta, pyramid, long prism, or broken wheel. This is exactly
the statement of Lemma 6.2. ∎

######  Lemma 6.4.

Let $G$ be a diamond-free graph that belongs to $\mathcal{G}_{2}$. Then $G$ is
(theta, pyramid, long prism, wheel)-free.

###### Proof.

Clearly, every wheel either contains an induced diamond or is a broken wheel.
The result now follows from Corollary 6.3. ∎

######  Lemma 6.5.

Let $G$ be a (diamond, theta, pyramid, long prism, wheel)-free graph that
contains an induced $\overline{C_{6}}$. Then either $G$ is a complete prism,
or $G$ admits a clique-cutset.

###### Proof.

Recall that $\overline{C_{6}}$ is a short 3-prism; fix a maximum integer
$n\geq 3$ such that $G$ contains an induced short $n$-prism $H$. Set
$V(H)=A\cup B$, where $A=\\{a_{1},\dots,a_{n}\\}$ and
$B=\\{b_{1},\dots,b_{n}\\}$ are disjoint, $n$-vertex cliques, such that for
all $i,j\in\\{1,\dots,n\\}$, $a_{i}$ is adjacent to $b_{j}$ in $H$ if and only
if $i=j$. We may assume that $V(H)\subsetneqq V(G)$, for otherwise, $G$ is a
complete prism, and we are done. We may further assume that $G$ is connected,
for otherwise, $\emptyset$ is a clique-cutset of $G$, and again we are done.

Claim 1. For all $v\in V(G)\setminus V(H)$, either $N_{G}(v)\cap V(H)=A$, or
$N_{G}(v)\cap V(H)=B$, or there exists some $i\in\\{1,\dots,n\\}$ such that
$N_{G}(v)\cap V(H)\subseteq\\{a_{i},b_{i}\\}$.

_Proof of Claim 1._ Fix $v\in V(G)\setminus V(H)$. We may assume that
$|N_{G}(v)\cap V(H)|\geq 2$, for otherwise, the result is immediate. Next, if
there exist distinct $i,j\in\\{1,\dots,n\\}$ such that $v$ is complete to
$\\{a_{i},b_{j}\\}$, then $G[v,a_{i},a_{j},b_{i},b_{j}]$ is either a theta or
a wheel, contrary to the fact that $G$ is (theta, wheel)-free. So, if $v$ has
a neighbor both in $A$ and in $B$, then there exists some
$i\in\\{1,\dots,n\\}$ such that $N_{G}(v)\cap V(H)=\\{a_{i},b_{i}\\}$, and we
are done. From now on, we assume that either $N_{G}(v)\cap V(H)\subseteq A$ or
$N_{G}(v)\cap V(H)\subseteq B$; by symmetry, we may assume that $N_{G}(v)\cap
V(H)\subseteq A$, and we deduce that $|N_{G}(v)\cap A|\geq 2$. Then $v$ is
complete to $A$, for otherwise, we fix pairwise distinct $a_{i},a_{j},a_{k}\in
A$ such that $v$ is adjacent to $a_{i},a_{j}$ and nonadjacent to $a_{k}$, and
we observe that $G[v,a_{i},a_{j},a_{k}]$ is a diamond, contrary to the fact
that $G$ is diamond-free. It now follows that $N_{G}(v)\cap V(H)=A$, and we
are done. This proves Claim 1. $\blacklozenge$

Claim 2. If there exists some $v\in V(G)\setminus V(H)$ such that
$N_{G}(v)\cap V(H)=A$ (resp. such that $N_{G}(v)\cap V(H)=B$), then $A$ (resp.
$B$) is a clique-cutset of $G$.

_Proof of Claim 2._ By symmetry, we may assume that some $v\in V(G)\setminus
V(H)$ satisfies $N_{G}(v)\cap V(H)=A$; we must show that $A$ is a clique-
cutset of $G$. By construction, $A$ is a clique of $G$, and so it suffices to
show that $A$ is a cutset of $G$ separating $v$ from $B$. Suppose otherwise.
Then there exists an induced path $P$ in $G\setminus V(H)$ between $v$ and
some vertex that has a neighbor in $B$. Let $Q=q_{0},\dots,q_{t}$ (with $t\geq
0$) be minimum-length subpath of $P$ such that $q_{0}$ is complete to $A$ and
$q_{t}$ has a neighbor in $B$; by Claim 1, $N_{G}(q_{0})\cap V(H)=A$ and
$q_{0}\neq q_{t}$, i.e., $t\geq 1$. By symmetry, we may assume that $q_{t}$ is
adjacent to $b_{1}$. By Claim 1, we have that either $N_{G}(q_{t})\cap
V(H)=B$, or $N_{G}(q_{t})\cap V(H)=\\{a_{1},b_{1}\\}$, or $N_{G}(q_{t})\cap
V(H)=\\{b_{1}\\}$.

Assume first that $N_{G}(q_{t})\cap V(H)=B$. If $t=1$, then $G[A\cup
B\cup\\{q_{0},q_{1}\\}]$ is a short $(n+1)$-prism, contrary to the maximality
of $n$. So, $t\geq 2$. By the minimality of $Q$, all internal vertices of $Q$
are anticomplete to $B$. If the internal vertices of $Q$ are also anticomplete
to $A$, then $G[\\{a_{1},a_{2},b_{1},b_{2}\\}\cup V(Q)]$ is a long prism,
contrary to the fact that $G$ is long-prism-free. Hence, some internal vertex
of $Q$ has a neighbor in $A$; let $i\in\\{1,\dots,t-1\\}$ be maximum with the
property that $q_{i}$ has a neighbor in $A$. By the minimality of $Q$, and by
Claim 1, we know that $q_{i}$ has a unique neighbor in $A$; fix
$j\in\\{1,\dots,n\\}$ such that $a_{j}$ is the unique neighbor of $q_{i}$ in
$A$, and fix any $k\in\\{1,\dots,n\\}\setminus\\{j\\}$. But now
$G[a_{j},a_{k},b_{j},b_{k},q_{i},q_{i+1},\dots,q_{t}]$ is a pyramid, contrary
to the fact that $G$ is pyramid-free.

Assume next that $N_{G}(q_{t})\cap V(H)=\\{a_{1},b_{1}\\}$. Let $q_{i}$ be the
vertex of $Q$ with highest index such that $q_{i}$ is adjacent to $a_{2}$.
Then $q_{i},\ldots,q_{t},b_{1},b_{2},a_{2},q_{i}$ is a hole, and $a_{1}$ has
at least three neighbors (namely, $a_{2},q_{t},b_{1}$) in it, contrary to the
fact that $G$ is wheel-free.

Assume finally that $N_{G}(q_{t})\cap V(H)=\\{b_{1}\\}$. Let $q_{i}$ (resp.
$q_{j}$) be the vertex of $Q$ with highest index such that $q_{i}$ (resp.
$q_{j}$) is adjacent to $a_{2}$ (resp. $a_{1}$). If $j\geq i$ then
$q_{i},\ldots,q_{t},b_{1},b_{2},a_{2},q_{i}$ is a hole and $a_{1}$ has at
least three neighbors in it (namely, $a_{2},q_{j},b_{1}$), contrary to the
fact that $G$ is wheel-free. So, $i>j$. Then
$q_{j},\ldots,q_{t},b_{1},a_{1},q_{j}$ is a hole and $a_{2}$ has two
nonadjacent neighbors in it (namely, $a_{1},q_{i}$), and hence
$G[q_{j},\dots,,q_{t},b_{1},a_{1},a_{2}]$ is a theta or a wheel, contrary to
the fact that $G$ is (theta, wheel)-free. This proves Claim 2. $\blacklozenge$

In view of Claims 1 and 2, we assume from now on that for all $v\in
V(G)\setminus V(H)$, there exists some $i\in\\{1,\dots,n\\}$ such that
$N_{G}(v)\cap V(H)\subseteq\\{a_{i},b_{i}\\}$.

Claim 3. For all $i\in\\{1,\dots,n\\}$, if some vertex in $V(G)\setminus V(H)$
is complete to $\\{a_{i},b_{i}\\}$, then $\\{a_{i},b_{i}\\}$ is a clique-
cutset of $G$.

_Proof of Claim 3._ By symmetry, we may assume that some vertex of
$V(G)\setminus V(H)$ is complete to $\\{a_{1},b_{1}\\}$; we must show that
$\\{a_{1},b_{1}\\}$ is a clique-cutset of $G$. Let $p_{0}$ be a vertex of
$V(G)\setminus V(H)$ that is complete to $\\{a_{1},b_{1}\\}$. Since $a_{1}$ is
adjacent to $b_{1}$, it suffices to show that $G\setminus\\{a_{1},b_{1}\\}$ is
disconnected. Suppose otherwise. Then, there exists an induced path in
$G\setminus\\{a_{1},b_{1}\\}$ from the vertex $p_{0}$ to a vertex in
$V(H)\setminus\\{a_{1},b_{1}\\}$. Consequently, there exists an induced path
$P=p_{0},\dots,p_{s}$ (with $s\geq 0$) in $G\setminus(A\cup B)$ such that
$p_{s}$ has a neighbor in $V(H)\setminus\\{a_{1},b_{1}\\}$; we may assume that
the path $P$ was chosen so that its length is minimum. By Claim 1, we have
that $N_{G}(p_{0})\cap V(H)=\\{a_{1},b_{1}\\}$, and so $s\geq 1$. Furthermore,
by the minimality of $P$, $\\{p_{0},\dots,p_{s-1}\\}$ is anticomplete to
$V(H)\setminus\\{a_{1},b_{1}\\}$. By symmetry, we may assume that $a_{2}\in
N_{G}(p_{s})\cap V(H)\subseteq\\{a_{2},b_{2}\\}$. Let $i$ be the largest index
in $\\{0,\dots,s\\}$ such that $p_{i}$ is adjacent to $b_{1}$ (such an $i$
exists because $p_{0}$ is adjacent to $b_{1}$). Now
$p_{i},\dots,p_{s},a_{2},a_{3},b_{3},b_{1},p_{i}$ is a hole, and $a_{1}$ has
at least three neighbors (namely, $a_{2},a_{3},b_{1}$) in it, contrary to the
fact that $G$ is wheel-free. This proves Claim 3. $\blacklozenge$

In view of Claim 3, we may now assume that no vertex in $V(G)\setminus V(H)$
has more than one neighbor in $V(H)$. Let $N_{A}$ be the set of all vertices
in $V(G)\setminus V(H)$ that have a neighbor in $A$, and let $N_{B}$ be the
set of all vertices in $V(G)\setminus V(H)$ that have a neighbor in $B$. Then
$N_{A}\cap N_{B}=\emptyset$. Since $V(H)\subsetneqq V(G)$ and $G$ is
connected, we have that $N_{A}\cup N_{B}\neq\emptyset$. If $N_{A}=\emptyset$,
then $B$ is a clique-cutset of $G$, and if $N_{B}=\emptyset$, then $A$ is a
clique-cutset of $G$. So, we may assume that $N_{A}$ and $N_{B}$ are both
nonempty. Furthermore, we may assume that there is an induced path in
$G\setminus V(H)$ between $N_{A}$ and $N_{B}$, for otherwise, both $A$ and $B$
are clique-cutsets of $G$, and we are done. Let $P=p_{0},\dots,p_{s}$ (with
$s\geq 0$) be a minimum-length path in $G\setminus V(H)$ such that $p_{0}\in
N_{A}$ and $p_{s}\in N_{B}$; since $N_{A}\cap N_{B}=\emptyset$, we see that
$s\geq 1$. Furthermore, the minimality of $P$ implies that the interior of $P$
is anticomplete to $V(H)$.

Since no vertex of $V(G)\setminus V(H)$ has more than one neighbor in $V(H)$,
we may assume by symmetry that $N_{G}(p_{0})\cap V(H)=\\{a_{1}\\}$, and that
either $N_{G}(p_{s})\cap V(H)=\\{b_{1}\\}$ or $N_{G}(p_{s})\cap
V(H)=\\{b_{2}\\}$. But if $N_{G}(p_{s})\cap V(H)=\\{b_{2}\\}$, then
$G[a_{1},a_{2},b_{1},b_{2},p_{0},\dots,p_{s}]$ is a theta, contrary to the
fact that $G$ is theta-free. So, $N_{G}(p_{s})\cap V(H)=\\{b_{1}\\}$. We now
have that $V(P)$ is anticomplete to $V(H)\setminus\\{a_{1},b_{1}\\}$.

Our goal is to show that $\\{a_{1},b_{1}\\}$ is a clique-cutset of $G$.
Suppose otherwise; then $G\setminus\\{a_{1},b_{1}\\}$ is connected. Then,
there exists an induced path in $G\setminus\\{a_{1},b_{1}\\}$ from a vertex in
$P$ to a vertex in $V(H)\setminus\\{a_{1},b_{1}\\}$. Since $V(P)$ is
anticomplete to $V(H)\setminus\\{a_{1},b_{1}\\}$, any such path has length at
least two. Deleting the endpoints of any such path, we obtain an induced path
$Q=q_{0},\dots,q_{t}$ (with $t\geq 0$) in $G\setminus(V(H)\cup V(P))$ such
that $q_{0}$ has a neighbor in $V(P)$, and $q_{t}$ has a neighbor in
$V(H)\setminus\\{a_{1},b_{1}\\}$; we may assume that $Q$ is a minimum-length
path with this property, so that $q_{0}$ is the only vertex of $Q$ with a
neighbor in $V(P)$, and $q_{t}$ is the only vertex of $Q$ with a neighbor in
$V(H)\setminus\\{a_{1},b_{1}\\}$. By symmetry, we may further assume that
$q_{t}$ is adjacent to $a_{2}$; then $N_{G}(q_{t})\cap V(H)=\\{a_{2}\\}$. Let
$i$ be the largest index in $\\{0,\dots,s\\}$ such that $q_{0}$ is adjacent to
$p_{i}$. Then
$p_{i},\dots,p_{s},b_{1},b_{3},a_{3},a_{2},q_{t},\dots,q_{0},p_{i}$ is a hole
in $G$, and $b_{2}$ has at least three neighbors (namely, $a_{2},b_{1},b_{3}$)
in it, contrary to the fact that $G$ is wheel-free. This completes the proof.
∎

######  Lemma 6.6.

Let $G$ be a (diamond, theta, pyramid, long prism, wheel)-free graph. Then
either $G$ is a complete prism, a cycle, or a complete graph, or $G$ admits a
clique-cutset.

###### Proof.

If $G$ contains an induced $\overline{C_{6}}$, then the result follows from
Lemma 6.5. Otherwise, we have that $G$ is (3PC, wheel)-free, and the result
follows from Theorem 6.1. ∎

######  Theorem 6.7.

Let $G$ be a diamond-free graph that belongs to $\mathcal{G}_{2}$. Then either
$G$ is a complete prism, a cycle, or a complete graph, or $G$ admits a clique-
cutset.

###### Proof.

This follows immediately from Lemmas 6.4 and 6.6. ∎

###  6.1 Algorithmic considerations

Clearly, complete prisms, cycles, and complete graphs are diamond-free and
belong to $\mathcal{G}_{2}$, and furthermore, they can all be recognized in
polynomial time. So, using Corollary 2.4 and Theorem 6.7, we show that
diamond-free graphs in $\mathcal{G}_{2}$ can be recognized in polynomial time.
In order to derive the result, we decompose a graph by means of clique-
cutsets. This common algorithmic tool, first proposed by Tarjan ([28]),
applies to any $n$-vertex graph $G$ and produces a family $\mathcal{H}$ of
$\mathcal{O}(n)$ induced subgraphs of $G$ that do not have any clique-cutsets
and such that $G$ can be obtained by an iterative application of gluing graphs
from $\mathcal{H}$ along cliques. The original algorithm proposed by Tarjan
runs in time $\mathcal{O}(n(n+m))$, where $m$ denotes the number of edges of
$G$. A more efficient approach for decomposing a graph along clique-cutsets
was suggested by Coudert and Ducoffe [14]. They improved the time complexity
to $\mathcal{O}(n^{\omega}\log n),$ where $\omega<2.3728596$ is the matrix
multiplication exponent (see [2]).

######  Proposition 6.8.

There exists an algorithm running in time $\mathcal{O}(n^{\omega}\log n)$ that
correctly determines if an input $n$-vertex graph $G$ is a diamond-free graph
in $\mathcal{G}_{2}$.

###### Proof.

Given a graph $G$ with $n$ vertices, testing if $G$ is diamond-free can be
done in time $\mathcal{O}(n^{\omega})$ (see [29]). Assuming $G$ is diamond-
free, we compute the connected components of $G$ and run the algorithm by
Coudert and Ducoffe [14] on each nontrivial component of $G$. This can be done
in time $\mathcal{O}(n^{\omega}\log n)$. The algorithm produces a family
$\mathcal{H}$ of $\mathcal{O}(n)$ induced subgraphs of $G$ that do not have
any clique-cutsets and such that $G$ can be obtained by an iterative
application of gluing graphs from $\mathcal{H}$ along cliques. We then check,
for each graph $H\in\mathcal{H}$, whether $H$ is a complete prism, cycle, or a
complete graph. If this is the case, the algorithm determines that $G$ belongs
to $\mathcal{G}_{2}$, and otherwise, it determines that $G$ does not belong to
$\mathcal{G}_{2}$. The correctness follows from Corollary 2.4 and Theorem 6.7.

To complete the proof, we show that testing whether a given $H\in\mathcal{H}$
satisfies one of the desired properties can be done in time
$\mathcal{O}(n+m)$, where $m$ denotes the number of edges of $G$. Since $H$ is
connected, testing if it is a cycle or a complete graph can be done in linear
time simply by checking if all the vertex degrees are equal to $2$ or to
$|V(H)|-1$, respectively. If none of these cases occurs, we can assume that
$n=2k$ for some $k\geq 3$ and that every vertex in $H$ has degree exactly $k$,
since otherwise, we can infer that $H$ is not a complete prism. We choose an
arbitrary vertex $v\in V(H)$ and compute the components of the graph
$H[N_{H}(v)]$. If $H$ is a short $k$-prism, then $H[N_{H}(v)]$ has exactly two
components, say $C$ and $D$, such that $C$ is isomorphic to a complete graph
$K_{k-1}$ and $D$ is a trivial component. Set $A=C\cup\\{v\\}$ and
$B=V(G)\setminus A$. Since we already checked that all the vertices are of
degree $k+1$, it remains to verify if $B$ is a clique of cardinality $k$. If
this is the case, then $H$ is a complete prism, otherwise it is not. Each of
the above constantly many steps can be carried out in linear time. ∎

Moreover, it is clear that the Maximum Weight Clique, Maximum Weight Stable
Set, and Vertex Coloring can be solved in polynomial time for complete prisms,
cycles, and complete graphs. Thus, Theorem 6.7 and the algorithm by Coudert
and Ducoffe [14] allow us to solve these three optimization problems in
polynomial time for diamond-free graphs in $\mathcal{G}_{2}$. A more precise
time complexity analysis is provided by the following.

######  Theorem 6.9.

When restricted to the class of diamond-free graphs in $\mathcal{G}_{2}$ with
$n$ vertices and $m$ edges, the Maximum Weight Clique and Vertex Coloring
problems can be solved in $\mathcal{O}(n^{\omega}\log n)$ time and the Maximum
Weight Stable Set problem in $\mathcal{O}(n^{2}(n+m))$ time.

###### Proof.

Let $G$ be a diamond-free graph with $n$ vertices and $m$ edges that belongs
to $\mathcal{G}_{2}$. For the Maximum Weight Clique and Vertex Coloring
problems, the approach is as follows. We compute the connected components of
$G$ and run the algorithm by Coudert and Ducoffe [14] on each component of
$G$. This can be done in time $\mathcal{O}(n^{\omega}\log n)$. We obtain a
family $\mathcal{H}$ of $\mathcal{O}(n)$ induced subgraphs of $G$ that do not
have any clique-cutsets and such that $G$ can be obtained by an iterative
application of gluing graphs from $\mathcal{H}$ along cliques. We now iterate
over all $H\in\mathcal{H}$ and solve the Maximum Weight Clique and Vertex
Coloring problems on $H$ in linear time. By Theorem 6.7, each graph
$H\in\mathcal{H}$ is a complete prism, cycle, or a complete graph; as
explained in the proof of Proposition 6.8, which of these cases occurs can be
determined in linear time in the size of $H$. If $H$ is a complete graph, then
its chromatic number is $|V(H)|$ and its vertex set solves the Maximum Weight
Clique problem. Otherwise, if $H$ is a cycle with at least four vertices, then
its chromatic number is either $2$ or $3$, depending on whether $|V(H)|$ is
even or odd, respectively, and to solve the Maximum Weight Clique problem, we
only need to examine its edges. Finally, if $H$ is a complete prism, say with
$|V(H)|=2k$ for some $k\geq 3$, then we can identify in linear time the two
cliques $A$ and $B$, each of size $k$, that partition $V(H)$. Then, the
chromatic number of $H$ is $k$, and to solve the Maximum Weight Clique
problem, we only need to examine the two cliques $A$ and $B$ and the $k$ edges
connecting them. In all these cases, the Maximum Weight Clique and Vertex
Coloring problems can be solved in linear time for graphs in $\mathcal{H}$.
Since each clique of $G$ is fully contained in one of the graphs in
$\mathcal{H}$, this provides an efficient solution to the Maximum Weight
Clique problem on $G$. Similarly, the chromatic number of $G$ is the maximum
chromatic number of the graphs in $\mathcal{H}$.

For the Maximum Weight Stable Set problem, the approach is similar, except
that in each decomposition step decomposes $G$ along a cut-partition $(A,B,C)$
of $G$ such that $C$ is a clique and the subgraph of $G$ induced by $A\cup C$
belongs to $\mathcal{H}$. For each vertex $v\in C$, we determine a maximum-
weight stable set of the subgraph of $G$ induced by $A\setminus N_{G}(v)$, a
maximum-weight stable set of the subgraph of $G$ induced by $A$, redefine the
weights on $C$, and solve the problem recursively on the graph $G-A$. (We
refer to [28] for details; see also [9, Section 8.1].) Thus, we solve
$\mathcal{O}(|V(G)|)$ subproblems for each graph $H\in\mathcal{H}$ for a total
of $\mathcal{O}(|V(G)|^{2})$ subproblems. Each of these subproblems can be
solved in linear time. If $H$ is a complete graph, then a heaviest vertex
forms a maximum-weight stable set. If $H$ is a cycle, then we can use the fact
that cycles have bounded treewidth and apply the results from [3, 7]. Finally,
assume that $H$ is a complete prism. Then, for each vertex $v$ a maximum-
weight stable set $S_{v}$ containing $v$ can be computed in
$\mathcal{O}(|V(H)|)$ time: indeed, $S_{v}$ is of the form
$S_{v}=\\{v,z^{v}\\}$ where $z^{v}$ is a vertex of maximum weight among the
nonneighbors of $v$ in $H$. The heaviest among the sets $S_{v}$ forms a
maximum-weight stable set. The complexity of this approach is
$\mathcal{O}(|V(H)|^{2})$, which in this case is $\mathcal{O}(|V(H)|+|E(H)|)$.
∎

In conclusion, let us put the results of Theorem 6.9 in perspective by
comparing them with the known complexities of the three problems in the larger
classes of diamond-free graphs and graphs in $\mathcal{G}_{2}$. First, the
Vertex Coloring problem is NP-hard for diamond-free graphs [24], as well as
for graphs in $\mathcal{G}_{2}$, since it is already hard for the subclass of
circular-arc graphs [21]. The situation is somewhat different for the Maximum
Weight Stable Set problem, which is NP-hard (even in the unweighted case) in
the class of diamond-free graphs, as can be seen using Poljak’s reduction
[26], but solvable in $\mathcal{O}(n^{6})$ time for $n$-vertex graphs in
$\mathcal{G}_{2}$ (see Corollary 3.9).

Finally, while the Maximum Weight Clique problem is known to be solvable in
polynomial time both for diamond-free graphs as well as for graphs in
$\mathcal{G}_{2}$, the running time of the algorithm given by Theorem 6.9
improves on both time complexities. By Theorem 4.7, the problem can be solved
in $\mathcal{O}(n^{4})$ time for $n$-vertex graphs in $\mathcal{G}_{2}$. For
the class of diamond-free graphs, observe that every edge in such a graph is
contained in a unique maximal clique. Thus, a diamond-free graph with $n$
vertices and $m$ edges has $\mathcal{O}(n+m)$ maximal cliques, and the Maximum
Weight Clique problem can be solved in polynomial time by enumerating all
maximal cliques and returning one of maximum weight. Using, for example, the
maximal clique enumeration algorithm due to Makino and Uno [25], this would
result in an overall running time of $\mathcal{O}(n^{2.373}(n+m))$ on diamond-
free graphs with $n$ vertices and $m$ edges.

### Acknowledgement

The authors are grateful to the anonymous reviewers for their careful reading
of the manuscript and valuable suggestions.

## References

  * [1] P. Aboulker, P. Charbit, N. Trotignon, and K. Vušković.  Vertex elimination orderings for hereditary graph classes.  Discrete Mathematics, 338(5):825–834, 2015.
  * [2] J. Alman and V. Vassilevska Williams.  A refined laser method and faster matrix multiplication.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 522–539. [Society for Industrial and Applied Mathematics (SIAM)], Philadelphia, PA, 2021.
  * [3] S. Arnborg, J. Lagergren, and D. Seese.  Easy problems for tree-decomposable graphs.  J. Algorithms, 12(2):308–340, 1991.
  * [4] J. Backer.  Separator orders in interval, cocomparability, and AT-free graphs.  Discrete Applied Mathematics, 159(8):717–726, 2011.
  * [5] J. Beisegel, M. Chudnovsky, V. Gurvich, M. Milanič, and M. Servatius.  Avoidable vertices and edges in graphs: existence, characterization, and applications.  Discrete Appl. Math., 309:285–300, 2022.
  * [6] A. Berry and J.-P. Bordat.  Separability generalizes Dirac’s theorem.  Discrete Applied Mathematics, 84(1-3):43–53, 1998.
  * [7] H. L. Bodlaender.  A linear-time algorithm for finding tree-decompositions of small treewidth.  SIAM J. Comput., 25(6):1305–1317, 1996.
  * [8] H. L. Bodlaender and A. M. C. A. Koster.  Safe separators for treewidth.  Discrete mathematics, 306(3):337–350, 2006.
  * [9] V. Boncompagni, I. Penev, and K. Vušković.  Clique-cutsets beyond chordal graphs.  J. Graph Theory, 91(2):192–246, 2019.
  * [10] V. Bouchitté and I. Todinca.  Treewidth and minimum fill-in: grouping the minimal separators.  SIAM Journal on Computing, 31(1):212–232, 2001.
  * [11] S. Chaplick, M. Töpfer, J. Voborník, and P. Zeman.  On $H$-topological intersection graphs.  Algorithmica, 83(11):3281–3318, 2021.
  * [12] L. Chen, R. Kyng, Y. P. Liu, R. Peng, M. P. Gutenberg, and S. Sachdeva.  Maximum flow and minimum-cost flow in almost-linear time.  In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science—FOCS 2022, pages 612–623. IEEE Computer Soc., Los Alamitos, CA, [2022] ©2022.
  * [13] M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković.  Universally signable graphs.  Combinatorica, 17(1):67–77, 1997.
  * [14] D. Coudert and G. Ducoffe.  Revisiting decomposition by clique separators.  SIAM J. Discrete Math., 32(1):682–694, 2018.
  * [15] C. Dallard, M. Milanič, and K. Štorgel.  Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure.  arXiv preprint arXiv:2206.15092, 2022.
  * [16] C. Dallard, M. Milanič, and K. Štorgel.  Treewidth versus clique number. I. Graph classes with a forbidden structure.  SIAM J. Discrete Math., 35(4):2618–2646, 2021.
  * [17] C. Dallard, M. Milanič, and K. Štorgel.  Treewidth versus clique number. II. Tree-independence number.  J. Combin. Theory Ser. B, 164:404–442, 2024.
  * [18] G. A. Dirac.  On rigid circuit graphs.  Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 25:71–76, 1961.
  * [19] U. Faigle and G. Frahling.  A combinatorial algorithm for weighted stable sets in bipartite graphs.  Discrete Appl. Math., 154(9):1380–1391, 2006.
  * [20] A. Frank.  Some polynomial algorithms for certain graphs and hypergraphs.  In Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975),, Congressus Numerantium, No. XV,, pages 211–226, 1976.
  * [21] M. Garey, D. Johnson, G. Miller, and C. Papadimitriou.  The complexity of coloring circular arcs and chords.  SIAM Journal on Algebraic Discrete Methods, 1(2):216–227, 1980\.
  * [22] T. R. Hartinger and M. Milanič.  Partial characterizations of 1-perfectly orientable graphs.  J. Graph Theory, 85(2):378–394, 2017.
  * [23] P. Heggernes.  Minimal triangulations of graphs: a survey.  Discrete Mathematics, 306(3):297–317, 2006.
  * [24] D. Kráľ, J. Kratochvíl, Z. Tuza, and G. J. Woeginger.  Complexity of coloring graphs without forbidden induced subgraphs.  In Graph-theoretic concepts in computer science (Boltenhagen, 2001), volume 2204 of Lecture Notes in Comput. Sci., pages 254–262. Springer, Berlin, 2001.
  * [25] K. Makino and T. Uno.  New algorithms for enumerating all maximal cliques.  In Algorithm theory—SWAT 2004, volume 3111 of Lecture Notes in Comput. Sci., pages 260–272. Springer, Berlin, 2004.
  * [26] S. Poljak.  A note on stable sets and colorings of graphs.  Commentationes Mathematicae Universitatis Carolinae, 15(2):307–309, 1974.
  * [27] D. J. Rose, R. E. Tarjan, and G. S. Lueker.  Algorithmic aspects of vertex elimination on graphs.  SIAM Journal on computing, 5(2):266–283, 1976.
  * [28] R. E. Tarjan.  Decomposition by clique separators.  Discrete mathematics, 55(2):221–232, 1985.
  * [29] V. V. Williams, J. R. Wang, R. Williams, and H. Yu.  Finding four-node subgraphs in triangle time.  In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1671–1680. SIAM, Philadelphia, PA, 2015.
  * [30] Y. Ye and A. Borodin.  Elimination graphs.  ACM Transactions on Algorithms, 8(2):Article 14, 1–23, 2012.