# Contractions in perfect graphs

Alexandre Dupont-Bouillard, Pierre Fouilhoux, Roland Grappe, Mathieu Lacroix

► To cite this version:

Alexandre Dupont-Bouillard, Pierre Fouilhoux, Roland Grappe, Mathieu Lacroix. Contractions in perfect graphs. Discrete Applied Mathematics, 2025, 377, pp.380-389. 10.1016/j.dam.2025.07.022. hal-05361129

HAL Id: hal-05361129

https://hal.science/hal-05361129v1

Submitted on 20 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Contractions in perfect graphs

Alexandre Dupont-Bouillard<sup>a,b,*</sup>, Pierre Fouilhoux<sup>b</sup>, Roland Grappe<sup>c</sup>, Mathieu Lacroix<sup>b</sup>

<figure><img src="image_2.png" /></figure>

Check for
updates

## ARTICLE INFO

**Article history:**

Received 4 October 2024

Received in revised form 10 March 2025

Accepted 15 July 2025

Available online 4 August 2025

**Keywords:**

Perfect graphs

Contraction perfect graphs

co-2-plexes

Leap

Roussel and Rubio lemma

Induced matchings

## ABSTRACT

In this paper, we characterize in several manners the class of contraction perfect graphs which are the perfect graphs that remain perfect after the contraction of any edge set. We define the utter graph $u(G)$ which is the graph whose stable sets are in bijection with the co-2-plexes of $G$, and prove that $u(G)$ is perfect if and only if $G$ is contraction perfect. Moreover, we exhibit the strong link between co-2-plexes and induced matchings and discuss its consequences according to known results on these problems. This yields several classes of graphs for which the maximum weighted co-2-plex is solvable in polynomial time. Finally, we show how our results extend to a new class of graphs for which finding a maximum weighted induced matching can be done in polynomial time.

© 2025 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license ([http://creativecommons.org/licenses/by/4.0/](http://creativecommons.org/licenses/by/4.0/)).

## 0. Introduction

A graph $G$ is called perfect if $\omega(H) = \chi(H)$ for every induced subgraph $H$ of $G$, where $\omega(H)$ is the clique number of $H$ and $\chi(H)$ its chromatic number. Contracting any pair of vertices, that is, identifying both vertices, does not always preserve perfection. For instance, perfection is destroyed if there is an odd induced path of length at least 5 between those vertices.

Two nonadjacent vertices in a graph form an *even pair* if every induced path between them has an even number of edges. Fonlupt and Uhry [17] proved that contracting an even pair in a perfect graph preserves perfection, and Meyniel proved what is called the Even Pair Lemma [31]: no minimally imperfect graph contains an even pair. Concerning the associated decision problems, Bienstock [3] proved that both following are co-NP-complete in the general case: deciding whether a given pair of vertices of a graph forms an even pair, and deciding whether a given graph contains an even pair. A graph is *even-contractile* if either it is a clique or there exists a sequence $G_0, \dots, G_k$ of graphs such that $G = G_0, G_k$ is a clique and for $i = 0, \dots, k-1$, the graph $G_i$ has an even pair $(x, y)$ whose contraction yields $G_{i+1}$. A graph $G$ is *perfectly contractile* if every induced subgraph of $G$ is even contractile.

In this paper, we approach contractions in perfect graphs with a slightly different point of view: we are interested in the graphs for which the contraction of any set of edges preserves perfection, and we call them *contraction perfect*. Since perfection is preserved under taking induced subgraphs, contraction perfect graphs can be seen as the graphs in which every induced minor is perfect, where an *induced minor* is a graph obtained by deleting vertices and contracting edges.

<footnote><sup>a</sup> LIMOS CNRS UMR 6158 Université Clermont Auvergne, 24 Av. des Landais, Aubière, 63170 France</footnote>

<footnote><sup>b</sup> LIPN CNRS UMR 7030 Université Sorbonne Paris Nord, 99 Av. Jean Baptiste Clément, Villetaneuse, 93430 France</footnote>

<footnote><sup>c</sup> LAMSADE CNRS UMR 7243 Université Paris Dauphine-PSL, Pl. du Maréchal de Lattre de Tassigny, Paris, 75016 France</footnote>

<footnote>* Corresponding author.</footnote>

<footnote>E-mail addresses: dupont-bouillard@lipn.fr (A. Dupont-Bouillard), fouilhoux@lipn.fr (P. Fouilhoux), roland.grappe@lamsade.dauphine.fr (R. Grappe), lacroix@lipn.fr (M. Lacroix).</footnote>
A class of graphs is *induced minor closed* if, for any element of that class, each of its induced minors also belongs to that class.

By definition, a perfect graph remains perfect by any vertex set deletion. Perfect graphs are characterized in terms of forbidden induced subgraphs, and this tremendous result is known as the *strong perfect graph theorem* [11]: a graph is perfect if and only if it contains no induced odd hole nor odd antihole. Since perfect graphs do not remain perfect by edge set contractions (a hole of length 6 — which is perfect — does not remain perfect by the contraction of a single edge), there is no characterization of perfect graphs by forbidden induced minors. An important ingredient of the proof of the strong perfect graph theorem has been called the “wonderful lemma” by the authors for its many applications, the latter turns out to be a rewriting of Roussel and Rubio’s lemma [36]. Thanks to even pairs, the proof of the strong perfect graph theorem has been shortened [13].

By definition of contraction perfect graphs, a characterization in terms of forbidden induced minors can be directly deduced from the strong perfect graph theorem. Indeed, if a graph is not contraction perfect, then there exist an edge set contraction and a vertex set deletion that gives an odd hole or an odd antihole. Therefore, odd holes and odd antiholes are the induced minors to be forbidden to ensure contraction perfection. The strong perfect graph theorem proves that this induced minor characterization is minimal.

In this article, we give the minimal induced subgraph characterization of contraction perfect graphs.

A co-2-plex is a subset of vertices inducing a subgraph of maximum degree at most one. This notion, or rather its complement version, was introduced in 1978 by Seidman and Foster [37] to seek communities in a graph with more freedom than when looking for cliques — a *clique* is a set of pairwise adjacent vertices. Indeed, a *k-plex* is a set $W$ of vertices inducing a graph where every vertex has degree at least $|W| - k$, and cliques are special cases of 2-plexes. The underlying optimization problem is to find a maximum weighted $k$-plex in a given weighted graph. For any fixed $k$ and hence for $k=2$, this problem is NP-hard [1]. Hence, by complementing the graph, so is the problem of finding a maximum co-2-plex. It turns out that the latter optimization problem, which can be seen as a relaxation of the maximum stable set problem — a *stable set* is a set of vertices inducing a subgraph of maximum degree at most 0 — behaves well in contraction perfect graphs.

This topic has been especially lively the past few years, mostly in the design of practical algorithms that find a maximum weighted $k$-plex. For this problem, there are exact algorithms [44], algorithms based on local search [9,10,26,35], heuristics [42], branch and bound algorithms, some of which incorporate machine learning ingredients [1,7,23,25,34,41,43], and quadratic models [38]. From a more combinatorial optimization point of view, a combinatorial algorithm is devised in [30], and polyhedral studies are conducted in [1,29]. The problem of enumerating the $k$-plexes also received some attention [15,24,40]. In [32], the authors provided a parameterized algorithm and heuristics for the maximum co-$k$-plex problem.

**Contributions.** We first introduce the class of contraction perfect graphs and characterize them in several manners. We show how this class of graphs arises naturally when studying the problem of finding a maximum weighted co-2-plex of a graph. This result comes from the study of an auxiliary graph that we called the *utter graph* $u(G)$ in which the stable sets are in bijection with the co-2-plexes of $G$. We showed that $G$ is contraction perfect if and only if $u(G)$ is perfect. Surprisingly, every perfect utter graph is also contraction perfect. For this reason, we investigate sufficient conditions on a class of graphs $C$ for the following to hold: $G \in C \Leftrightarrow u(G) \in C$. By exhibiting the strong link between co-2-plexes and induced matchings, we show that finding a maximum weighted induced matching can be done in polynomial time on contraction perfect graphs. This allows us to prove that finding a maximum weighted co-2-plex can be done in polynomial time on interval filament graphs, circular arc graphs, and asteroidal triple free graphs.

**Definitions.** All the graphs in this paper are simple and connected. Given a graph $G = (V, E)$, we denote its complement by $\bar{G} = (V, \bar{E})$, where $\bar{E} = \{uv : uv \notin E\}$. We denote by $V(G)$ (resp. $E(G)$) the vertex (resp. edge) set of $G$. Two vertices $u$ and $v$ are *adjacent* if $uv \in E(G)$. Given two disjoint subsets of vertices $U$ and $W$, $U$ is *complete* (resp. *anticomplete*) to $W$ if every vertex of $U$ is adjacent (resp. nonadjacent) to every vertex of $W$. When $U$ is a singleton $\{u\}$, we write that $u$ is complete (resp. anticomplete) to $W$. A vertex $u$ is *universal* if it is complete to $V \setminus u$. Given a subset of vertices $W \subseteq V$, let $E(W)$ denote the set of edges of $G$ having both endpoints in $W$ and $\delta(W)$ the set of all edges having exactly one endpoint in $W$. When $W$ is a singleton $\{w\}$, we will simply write $\delta(w)$, and $|\delta(w)|$ is the degree of $w$. We say that the edges in $\delta(w)$ are *incident* to $w$, and two edges sharing an extremity are said *adjacent*. A *matching* is a set of pairwise nonadjacent edges. An *induced matching* $M$ is a set of edges such that $G[V(M)]$ has maximum degree 1. Note that all induced matching are matching but the converse does not hold. For $F \subseteq E$, let $V(F)$ denote the set of vertices incident to any edge of $F$. Given $W \subseteq V$ (resp. $F \subseteq E$), the graph $G[W] = (W, E(W))$ (resp. $G[F] = (V(F), F)$) is the *subgraph induced by* $W$ (resp. $F$) in $G$. The set $W$ is said *connected* if $G[W]$ is. When $H$ is an induced subgraph of $G$, we say that $G$ contains $H$. Given a vertex $u \in V$, we denote by $N_G(u) = \{w \in V : uw \in E\}$ its *neighborhood* in $G$, and by $N_G[u] = N_G(u) \cup \{u\}$ its *closed neighborhood*. When the graph $G$ is clear from the context, we simply denote them by $N(u)$ and $N[u]$, respectively. Two vertices $u$ and $v$ are true (resp. false) twins if $N[u] = N[v]$ (resp. $N(u) = N(v)$).

A *path* (resp. *hole*) is a graph induced by a set of distinct vertices $\{v_1, \dots, v_p\}$ whose edge set is $\{v_i v_{i+1} : i = 1, \dots, p-1\}$ (resp. $\{v_i v_{i+1} : i = 1, \dots, p-1\} \cup \{v_1 v_p\}$ with $p \ge 4$). Note that this definition usually corresponds to induced paths. A subset of vertices induces a path (resp. hole) if its elements can be ordered into a sequence inducing a path (resp. hole). An *antipath* (resp. *antihole*) of $G$ is a path (resp. hole) of $\bar{G}$. The *length* of a hole or path is its number of edges. The *length*
of an antihole or antipath is the length of its complement. A path, antipath, hole or antihole of length at least 5 is called long. The parity of a path, antipath, hole, antihole is the parity of its length. The distance between two nodes is the length of the smallest path between them. The interior of a path or an antipath induced by $(v_1, \dots, v_p)$ is the graph induced by $(v_2, \dots, v_{p-1})$.

A pendant edge $uv \in E$ is such that one of $u$ or $v$ has degree one. The contraction of an edge $uv$ in $G$ consists in deleting $u$ and $v$, and adding a new vertex $w$ and the edges $wz$ for all $z \in N(u) \cup N(v)$. This new graph is denoted $G/uv$. For $F \subseteq E$, we denote by $G/F$ the graph obtained from $G$ by contracting all the edges in $F$. The image of a vertex $v$ of $G$ in $G/F$ is the vertex of $G/F$ to which $v$ is contracted, and the image of a set of edges $L$ is the set of the images of the vertices of $V(L)$ in $G/F$. An edge $uv$ and a vertex $w$ are adjacent by contraction if $w$ is adjacent to $x_{uv}$ in $G/uv$, where $x_{uv}$ is the image of $uv$ in $G/uv$. In other words, at least one of $uw$ and $vw$ is in $E$. Two edges $uv$ and $xy$ are adjacent by contraction if contracting both edges results in two adjacent vertices, that is, $\delta(\{u, v\}) \cap \delta(\{x, y\}) \neq \emptyset$.

The girth of a graph is the length of its smallest hole. A tree decomposition of a graph $G = (V, E)$ is a tree whose vertices $V_1, \dots, V_k$ are subsets of $V$ such that:

* if $V_i$ and $V_j$ both contain a vertex $v \in V$, all nodes in the unique path between $V_i$ and $V_j$ contains $v$.

* for every $uv \in E$ there is a $V_i$ that contains both $u$ and $v$.

The width of a tree decomposition is the size of its largest $V_i$ minus one. The treewidth of a graph $G$ is the minimum width of a tree decomposition of $G$.

Given a total order on a finite set of elements, an interval is a subset of consecutive elements following that order. The interval graph $G_I$ of a given finite set of intervals $I$ is the graph having one vertex per interval in $I$ and an edge between two vertices if their corresponding intervals have a nonempty intersection.

The line graph $L(G)$ of a graph $G = (V, E)$ is a graph having $E$ as vertex set and where two vertices are adjacent if the corresponding edges of $G$ are adjacent. The square $G^2$ of a graph $G = (V, E)$ is the graph having $V$ as vertex set and where two vertices are adjacent if the corresponding vertices of $G$ are adjacent or at distance two.

A coloring of a graph is an assignment of colors to its vertices such that two adjacent vertices have different colors, it is optimal if there exists no coloring using a smaller amount of colors.

# 1. Contraction perfect graphs

In this section, we first characterize contraction perfect graphs in several manners. We then establish the links between this new graph class and some other subclasses of perfect graphs.

## 1.1. Characterizing contraction perfect graphs

We investigate how contracting edges in a perfect graph impacts its perfection. We rely on the strong perfect graph theorem [11], which states that perfect graphs are the graphs that contain neither odd holes nor odd antiholes. We will also use the so-called wonderful lemma. It has been used extensively to prove the strong perfect graph theorem. The latter has been proved by Roussel and Rubio [36], another version has been proposed by Chudnovsky et al. [11], and finally a last version by Trotignon et al. [28]. We will use the following version of Chudnovsky et al. [11] (written for the complement graph).

**Lemma 1.1 ([11]).** Let $G = (V, E)$ be a perfect graph, and let $W \subseteq V$ be a connected set of vertices. Let $P$ be a long odd antipath of $G \setminus W$, whose extremities are anticomplete to $W$. One of the two following holds:

* a vertex of the interior of $P$ is anticomplete to $W$,

* there exists an antipath between two members of $W$ with the same interior as $P$.

In our settings, a rewriting of the wonderful lemma will be more convenient. This rewriting goes through the use of expanded antiholes defined as follows.

**Definition 1.2.** An edge $e$ and an odd antipath $P$ induced by $(w_1, \dots, w_p)$ with $p \ge 6$ form an expanded antihole if one extremity of $e$ is complete to $V(P) \setminus \{w_1, w_{p-1}, w_p\}$ and anticomplete to $\{w_1, w_{p-1}, w_p\}$, while the other extremity is complete to $V(P) \setminus \{w_1, w_2, w_p\}$ and anticomplete to $\{w_1, w_2, w_p\}$.

**Fig. 1** represents an expanded antihole where $(w_1, \dots, w_p)$ induces an odd antipath. An edge $e$ is involved in an expanded antihole if there exists an odd antipath forming an expanded antihole with $e$. Note that, by definition of an expanded antihole, the extremities of $e$ are not vertices of $P$, and contracting $e$ yields an odd antihole. Moreover, if $e = uv$, either $(u, w_2, \dots, w_{p-1}, v)$ or $(v, w_2, \dots, w_{p-1}, u)$ induces an odd antipath that forms an expanded antihole with edge $w_1w_p$. Note that $u, v$, and $P$ form a leap [39] in the complement graph.

**Lemma 1.3.** Let $G = (V, E)$ be a perfect graph and $F \subseteq E$ be a set of edges inducing a connected subgraph. If $G/F$ is an odd antihole of length at least 7, then $G$ contains an expanded antihole involved by an edge of $F$ and the odd antipath $G \setminus V(F)$.
<figure><img src="image_3.png" /><figcaption>**Fig. 1.** An expanded antihole.</figcaption></figure>

**Proof.** As $G/F$ is an odd antihole, it contains an odd antipath induced by $P = (p_1, \dots, p_k)$ forming an odd antihole with the image $p_0$ of $F$. Moreover, in $G, \{p_1, p_k\}$ is anticomplete to $V(F)$, and each vertex in the interior of $P$ is not anticomplete to $V(F)$. By Lemma 1.1 applied to $W = V(F)$, there exists an edge $uv \in F$ such that $(v, p_2, \dots, p_{k-1}, u)$ induces an odd antipath of $G$. Hence, $G$ contains an expanded antihole induced by the edge $uv$ and the antipath $(p_1, \dots, p_k)$. $\square$

Note that Lemma 1.3 is another version of Roussel and Rubio's lemma as Lemma 1.3 can be proved from Lemma 1.1 as follows. If every vertex in the interior of $P$ is not anticomplete to $W$, then contracting $W$ yields an odd antihole. By Lemma 1.3, the graph contains an expanded antihole given by an edge $uv$ and the antipath $P$. By definition of expanded antiholes, $u, v$, and the interior of $P$ induce an antipath.

Lemma 1.3 will be used to characterize when contracting an edge set of a perfect graph yields an odd antihole. The other case of imperfect structures appearing when contracting an edge set is when an odd hole appears. It will be dealt with using the following lemma.

**Lemma 1.4.** If $G/F$ contains a hole $H$ for some edge set $F$, then $G$ contains a hole of length at least $|V(H)|$.

**Proof.** We proceed by induction on $|F|$. The result holds if $|F| = 0$. Otherwise, some vertex $v$ of $H$ is obtained by contracting the edges of a connected subgraph $(V', F')$ of $G$ with $\emptyset \neq F' \subseteq F$. Let $a$ and $b$ be the neighbors of $v$ in $H$, and let $P$ be an ab-path in $G[V' \cup \{a, b\}]$. Then, $V(H) \setminus \{v\} \cup V(P)$ induces a hole of $G/(F \setminus F')$ of length at least $|V(H)|$, and induction concludes. $\square$

Now, we show the equality between the class of perfect graphs remaining perfect when contracting a single edge and the class of perfect graphs remaining perfect when contracting any edge set. This characterization yields as a byproduct the induced subgraph characterization of this graph class.

**Theorem 1.5.** Given a perfect graph $G$, the following are equivalent:

(i) $G$ is contraction perfect, that is, $G/F$ is perfect for all $F \subseteq E$,

(ii) $G/e$ is perfect for all $e \in E$,

(iii) $G$ contains no long hole and no expanded antihole.

**Proof.** The following implications are immediate: (i) $\Rightarrow$ (ii) $\Rightarrow$ (iii). We now prove (iii) $\Rightarrow$ (i). By contradiction, suppose that $G/F$ is not perfect for some minimal set of edges $F \subseteq E$.

If $G/F$ contains an odd hole, by Lemma 1.4, there exists a long hole in $G$, a contradiction.

Hence, by the strong perfect graph theorem, $G/F$ contains a long odd antihole induced by $(p_0, \dots, p_k)$, where $k \ge 6$ is even. Suppose that $F$ induces a connected subgraph of $G$ and let $p_0$ be the unique image of $F$ in $G/F$. Then Lemma 1.3 gives the existence of an expanded antihole in $G$ induced by $(p_1, \dots, p_k)$ and an edge of $F$, a contradiction.

Therefore, $F$ induces a disconnected set of vertices. There exist $F_0, F_i \subseteq F$ verifying $V(F_i) \cap V(F_0) = \emptyset$ such that $p_0$ and $p_i$ are respectively the images of $F_0$ and $F_i$ in $G/F$. By Lemma 1.3, there exists an edge $u_0v_0$ (resp. $u_iv_i$ with $1 \le i \le \frac{k}{2}$ up to node relabeling) of $F_0$ (resp. $F_i$) that forms an expanded antihole of $G/(F \setminus F_0)$ (resp. $G/(F \setminus F_i)$) with the antipath $(p_1, \dots, p_k)$ (resp. $(p_{i+1}, \dots, p_{i-1}$)). By definition of expanded antiholes, without loss of generality, suppose that $u_0$ (resp. $u_i$) is adjacent to $p_2$ (resp. $p_{i-2}$) but not to $p_{k-1}$ (resp. $p_{i+2}$). Hence, $H_{u_0} = (u_0, p_1, \dots, p_{k-1})$ induces an even antihole of
<figure><img src="image_4.png" /><figcaption>**Fig. 2.** Illustration for the proof of **Theorem 1.5**: the odd antihole $H_u \cup u' \setminus \{p_i, p_{i+1}\}$ is given in light gray.</figcaption></figure>

$G/(F \setminus F_i)$. Fig. 2 gives an illustration of $H_{u_0} \cup \{u_i\} \setminus \{p_i, p_{i+1}\}$ which induces an antihole in $G/(F \setminus F_0 \setminus F_i)$ of length $k-1$, and hence is odd. This contradicts the minimality assumptions on $F$. □

**Theorem 1.5** and the strong perfect graphs theorem imply the following characterization of contraction perfect graphs.

**Corollary 1.6.** A graph is contraction perfect if and only if it contains no long hole, no odd antihole, and no expanded antihole.

A graph is minimally non contraction perfect if it is not contraction perfect and each of its proper induced subgraphs is contraction perfect.

Note that the list of forbidden induced subgraphs of **Theorem 1.5** is inclusionwise minimal. Indeed, removing any vertex to each of these forbidden induced subgraphs yields a contraction perfect graph.

**Observation 1.7.** Expanded antiholes, odd antiholes, and long holes are minimally non contraction perfect.

**Proof.** Every proper induced subgraph of a hole is a set of disjoint paths, which means it contains no triangles and no holes. Then, it also contains no antiholes, expanded antiholes, or complements of expanded antiholes, since these graphs contain triangles. This implies that every proper subgraph of a hole and its complement are contraction perfect. Therefore, odd antiholes and long holes are minimally non contraction perfect.

We show that expanded antiholes are minimally non contraction perfect by considering the complement of an expanded antihole. Let us consider an expanded antihole $G$. Note that, $\bar{G}$ contains no antihole of length more than 6 since it contains precisely 6 vertices whose degree is greater or equal to 3, that are $W = \{u, v, w_1, w_2, w_{p-1}, w_p\}$. Indeed, since an antihole of length at least 6 is a regular graph whose vertices have degree at least 3, these are the only candidates that may belong to such an antihole. Since $\bar{G}[W]$ is not regular, it is not an antihole of length 6, this proves that $G$ does not contain any holes of length at least 6. Obviously, $\bar{G}$ does not contain any complement of an expanded antihole as proper induced subgraph. Now, note that the holes of $G$ are even, which means that $G$ only contains even antiholes and hence, no hole of length 5. By **Theorem 1.5**, expanded antiholes are minimally non-contraction perfect. □

We can devise from **Theorem 1.5** algorithms to recognize contraction perfect graphs, and to detect expanded antiholes in perfect graphs.

**Corollary 1.8.** Recognizing contraction perfect graphs can be done in polynomial time.

**Proof.** By **Theorem 1.5**, deciding whether a graph $G = (V, E)$ is contraction perfect amounts to check if $G$ is perfect and if, for each contraction of a single edge, the resulting graph is perfect. Each of these $|E| + 1$ perfection tests can be done in polynomial time [27]. □

**Corollary 1.9.** Detecting expanded antiholes in perfect graphs can be done in polynomial time

**Proof.** The algorithm is as follows: check whether the graph is contraction perfect by checking the perfection of each minor obtained by a single edge contraction (using our characterization). If the graph is contraction perfect, it does not contain any expanded antiholes. If not, by **Lemma 1.3**, it is sufficient to detect an odd antihole in one of the single-edge contraction minors, which can be done in polynomial time [12]. □
## 1.2. Relations to other graph classes

A prism is a graph that consists of two vertex disjoint triangles and three vertex disjoint paths, each of them having as extremities a vertex of each triangle. A prism is odd if its three vertex disjoint paths are odd. Grenoble graphs are the perfect graphs containing no long antiholes or odd prisms. They generalize Artemis graphs which are the perfect graphs containing no long antiholes or prisms. A graph is Meyniel if every odd cycle of length at least 5 has at least two chords. Artemis graphs and Meyniel graphs are known to be perfectly contractile [2,28]. Perfectly contractile graphs form a subclass of Grenoble graphs, and both classes are conjectured to be equal [16]. Given an ordered graph (G, <) (order < on its vertices), assigning the smallest color possible to each vertex following < is a greedy algorithm for computing a coloring however, it is not always optimal. Given an ordered graph (G, <), the ordering < is called perfect if for each induced ordered subgraph (H, <) the greedy algorithm produces an optimal coloring of H. The graphs admitting a perfect ordering are called perfectly orderable. They are proven to be perfectly contractile [2].

Note that the complement of a contraction perfect graph may not be contraction perfect. For instance, $\bar{C}_6$ is contraction perfect on the contrary to its complement. The complement graph of an expanded antihole formed by an edge $uv$ and an odd antipath $(w_1, \dots, w_p)$ is a prism formed by the triangles $\{u, w_1, w_2\}$, $\{v, w_p, w_{p-1}\}$, and its pairwise vertex disjoint path are $(u, w_p)$, $(w_2, \dots, w_{p-1})$, and $(w_1, v)$. For this reason, complements of expanded antiholes are special cases of odd prisms, which implies the following result.

**Observation 1.10.** Complements of Grenoble graphs are contraction perfect, hence in particular so are complements of Meyniel graphs, complements of Artemis graphs, and complements of perfectly orderable graphs.

Note that this inclusion is strict as the prism with two paths of length 3 and one of length 1 is not Grenoble but its complement is contraction perfect.

A graph is weakly chordal if it contains no long hole and no long antihole. As expanded antiholes contain even antiholes of length at least 6 we get the following.

**Observation 1.11.** A graph $G$ is weakly chordal if and only if $G$ and $\bar{G}$ are contraction perfect.

# 2. Utter graphs, co-2-plexes, and induced matchings

In this section, we start by defining the utter graph $u(G)$ whose stable sets are in bijection with the co-2-plexes of $G$. We provide sufficient conditions for a graph class $C$ to be closed by utter graph, meaning that $G$ belongs to $C$ if and only if $u(G)$ does. When a class $C$ satisfies these conditions and the maximum weighted stable set problem is polynomial in $C$, then so is the maximum weighted co-2-plex problem. In this way, we prove the polynomiality of the maximum co-2-plex on interval, chordal, circular arc, interval filament, weakly chordal, and asteroidal triple-free graphs, as finding a maximum weighted stable set can be done in polynomial time on these graphs [18–20]. A similar scheme has been used by Kathie Cameron [4–6] to give polynomial results for the maximum weighted induced matching problem by exhibiting a bijection between the induced matchings of a graph $G$ and the stable sets of $L(G)^2$. After that, we highlight the links between co-2-plexes and induced matchings. This permits us to prove that finding maximum weighted co-2-plexes or induced matchings can be done in polynomial time on contraction-perfect graphs.

## 2.1. Utter graphs and contraction perfect graphs

Let $S$ be a co-2-plex. The vertex edge representation of a $S$ is a couple $(W, F)$ where $W$ are the isolated vertices of $G[S]$ and $F$ are its isolated edges. Then, by definition of co-2-plexes, $F$ is an induced matching and contracting $F$ yields $|F|$ pairwise non-adjacent vertices and anticomplete to $W$. In other words, $W$ and the image of $F$ in $G/F$ form a stable set of $G/F$ of size $|W| + |F|$.

The utter graph $u(G)$ of a graph $G = (V, E)$ has vertex set $V \cup E$ and two vertices in $u(G)$ are adjacent if and only if their corresponding elements in $G$ are either adjacent, incident, or adjacent by contraction in $G$. Fig. 3 gives an illustration of this definition where the vertices 12 and 23 of $u(G)$ respectively correspond to the edges 12 and 23 of $G$. For each edge $uv$ of $G$, $G/uv$ is the subgraph of $u(G)$ induced by $V \cup \{uv\} \setminus \{u, v\}$ where $uv$ denotes the vertex of $u(G)$ associated with edges $uv$. Similarly, for a matching $F \subseteq E$, $G/F$ is the subgraph of $u(G)$ induced by $V \setminus V(F)$ and the vertices of $u(G)$ associated with edges in $F$.

**Lemma 2.1.** There is a bijection between the co-2-plexes of $G$ and the stable sets of $u(G)$.

**Proof.** By definition of utter graphs, a vertex subset $W$ and an edge set $F$ is a vertex edge representation $(W, F)$ if and only if $W \cup T$ is a stable set of $u(G)$. $\square$

We say that a graph class is *replicable* if adding true twins in any graph of that class yields another graph of that class.

**Theorem 2.2.** Let $C$ be an induced minor closed and replicable graph class, then $G \in C$ if and only if $u(G) \in C$.
<figure><img src="image_5.png" /><figcaption>**Fig. 3.** A graph G and its utter graph $u(G)$.</figcaption></figure>

**Proof.** ($\Leftarrow$) Since G is an induced subgraph of $u(G)$, the result follows from the assumptions on $C$.

($\Rightarrow$) Let $\tilde{G}$ be obtained from G by adding, for every edge $uv \in E$, a true twin $u'$ (resp. $v'$) to $u$ (resp. $v$). By construction, $\tilde{G}$ contains the edge $u'v'$. Let F be the set of $u'v'$ for every edge $uv \in E$. Note that $\tilde{G}/F = u(G)$ and that $\tilde{G}/F$ is obtained by adding true twins and contracting edges. Since $C$ is replicable and induced minor closed, $u(G)$ belongs to $C$. $\square$

**Theorem 2.2** gives conditions for graph classes to be closed by utter graphs without considering what Kathie Cameron [5] calls a "nice representations as intersection graphs" which is not always trivial to deduce from an arbitrary graph class definition. We denote by $u^k(G)$ the graph obtained by applying the utter graph transformation $k$ times.

As states the next observation, there exist graph classes that are closed by utter graph but that are not induced minor closed nor replicable.

**Observation 2.3.** The conditions given in *Theorem 2.2* are not necessary for a graph class to be closed by utter graph.

**Proof.** Consider the sequence $G_{i+1} = u(G_i)$, for $i \in \mathbb{Z}^+$, where $G_0 = C_4$. Let $C$ be the set of all $G_i$ completed by induction with the graphs whose utter graph is in $C$. Then, for any graph G and its utter graph $u(G)$, we have that $G \in C$ if and only if $u(G) \in C$. Note that each $G_i$ contains a $C_4$ and by construction, if $G$ is in $C$, then there exists $i \in \mathbb{Z}^+$ such that, $G = G_i$ or there exists $k \in \mathbb{Z}^+$ such that $u^k(G) = G_i$. Since G is a clique if and only if $u(G)$ is a clique, no element of $C$ is a clique, in particular $K_2 = (\{v_1, v_2\}, \{v_1v_2\})$ is not in $C$ but is an induced subgraph of every element in $C$. Hence $C$ is not induced minor closed. $\square$

As a consequence of **Theorem 1.5** we obtain the following.

**Corollary 2.4.** *Adding true or false twins preserves contraction perfection.*

Since the class of contraction perfect graphs is replicable by Corollary 2.4 and induced minor closed by definition, the following equivalence can be deduced from Theorem 2.2.

**Corollary 2.5.** *A graph is contraction perfect if and only if its utter graph is contraction perfect.*

Now, we show that contraction perfect graphs are precisely those for which the utter graph is perfect. This means that every perfect utter graph is also contraction perfect.

**Corollary 2.6.** *A graph is contraction perfect if and only if its utter graph is perfect.*

**Proof.** Let $G = (V, E)$ be a graph.

($\Leftarrow$) By definition of utter graphs, G and $G/e$ for $e \in E$ are induced subgraphs of $u(G)$. Hence, all those graphs are perfect since $u(G)$ is. By statement (ii) of *Theorem 1.5*, this implies that G is contraction perfect.

($\Rightarrow$) If G is contraction perfect, then so is $u(G)$ by Corollary 2.5. By definition of contraction perfect graphs, this implies that $u(G)$ is perfect. $\square$

## 2.2. Co-2-plexes and induced matchings

In this section, we highlight that the problems of maximum weighted co-2-plexes and induced matchings are strongly related by giving two simple reductions going from one problem to the other and deduce from these reductions corollaries on computational complexity for the maximum weighted co-2-plex problem.
Given a graph $G = (V, E)$, we denote by star$(G)$ the graph obtained by adding to each vertex $u$ a pendant edge $up_u$, where $p_u$ is a new vertex.

**Observation 2.7.** Given a graph $G = (V, E)$, we have $L(\mathrm{star}(G))^2 = u(G)$.

**Proof.** Identifying the vertices of $u(G)$ associated with $V$ to vertices $up_u$ of $L(\mathrm{star}(G))^2$ and identifying the vertices associated with $E$ in $u(G)$ to the ones associated with $E$ in $L(\mathrm{star}(G))^2$ gives the equality. $\square$

**Observation 2.8.** Finding a maximum $w$-weighted co-2-plex on $G = (V, E)$ is equivalent to finding a maximum $w'$-weighted induced matching on star$(G)$ where $w'_{uv} = \begin{cases} w_u & \text{if } v = p_u, \\ w_u + w_v & \text{otherwise,} \end{cases}$ for $uv \in E$.

Let us denote by $T(G)$ the graph obtained by adding a true twin to each vertex of the graph $G$.

**Observation 2.9.** Finding a maximum $w$-weighted induced matching on $G = (V, E)$ is equivalent to finding a maximum $w'$-weighted co-2-plex on $T(L(G)^2)$ where $w'_e = \begin{cases} \frac{w_e}{2} & \text{if } e \in E, \\ \frac{w_f}{2} & \text{if } e \text{ is the twin of } f. \end{cases}$

**Proof.** Let $F$ be a maximum induced matching of $G$ with respect to $w$. It corresponds to a maximum stable set $S$ of $L(G)^2$. Then, $S \cup S'$, where $S'$ is the set of twins of $S$, gives a co-2-plex of $T(L(G)^2)$ whose cost with respect to $w'$ is the same as $F$. Consider now a maximum co-2-plex $K$ with respect to $w'$. If a vertex $u$ belongs to $K$ and its twin $u'$ does not belong to $K$, by maximality there exists $v \in N(u)$ that belongs to $K$. Then, $K \cup u' \setminus v, K \setminus u \cup v'$ are co-2-plexes and one of them has a cost greater or equal to the one of $K$. Contracting the edges of $G[K]$ we obtain a stable set of $L(G)^2$ and hence an induced matching of $G$ with the same cost. $\square$

Note that the proof of **Observation 2.9** corresponds to the polynomial reduction showing that the maximum weighted 2-plex is NP-hard [1].

It is known that finding an induced matching of size $k$ is FPT when parameterized by the treewidth [8]. It is also FPT on line/bounded degree/planar and graphs with girth at least six when parameterized by $k$ [33].

Using **Observation 2.8** one eventually obtains the following.

**Corollary 2.10.** Finding a co-2-plex of size $k$ is FPT on bounded degree, planar graphs, and graphs with girth at least 6 when parameterized by $k$.

**Corollary 2.11.** Finding a co-2-plex of size $k$ can be done in polynomial time on bounded treewidth graphs.

**Proof.** Given a tree decomposition $(V_1, \dots, V_k)$ of $G$, we can construct a tree decomposition having the same width for star$(G)$ by adding a new neighbor $\{u, p_u\}$ to any vertex associated with a $V_i$ containing $u$. $\square$

Note that **Corollary 2.11** is also a consequence of Courcelle's theorem [14] as the property of having a co-$k$-plex of size $d$ is expressable in monadic second order logic (with a $d$ polynomial sized formula with monomials of degree $k$).

## 2.3. Polynomial results for the maximum co-2-plex and induced matching problems

In this section, we use **Theorem 2.2** to give new classes of graphs for which the maximum weighted co-2-plex problem is polynomial. As a byproduct, we obtain that the maximum weighted induced matching problem is solvable in polynomial time on contraction perfect graphs. Note that perfect graphs are not closed by utter graphs as $C_6$ is perfect, yet $u(C_6)$ is not as it contains several $C_5$.

Let us first start with a few definitions of graph classes. A $k$-hole free graph is a graph having no hole of length at least $k$. A *chordal graph* is a graph having no holes of length at least 4. A *circular arc graph* is a graph whose vertex set can be associated with intervals on a circle and where two vertices are adjacent if their corresponding intervals intersect. Note that circular arc graphs are not necessarily perfect. A *line interval* is a curve starting at the beginning of an interval on a line and finishing at the endpoint of this interval such that it lies on the upper half space of this line. An *interval filament graph* is a graph whose vertex set can be associated with line intervals and where two vertices are adjacent if their corresponding line intervals intersect. An *asteroidal triple* is a stable set of 3 vertices such that each pair of its vertices is linked by a path disjoint from the neighborhood of the third.

**Corollary 2.12.** Each of the following graph classes are closed by utter graphs: split, trivially perfect, interval, chordal, $k$-hole-free, circular arc, interval filament, and asteroidal triple-free graphs.

**Proof.** By **Theorem 2.2** it is sufficient to show that all these graph classes are induced minor closed and replicable.
**Trivially perfect.** Trivially perfect graphs are the graphs with no $P_4$ nor $C_4$ as induced subgraphs [21]. Hence, they are induced minor closed. Moreover, as $P_4$ and $C_4$ do not contain true twins, trivially perfect graphs are replicable.

**Interval graphs, circular arc, interval filament.** Contracting an edge $uv$ in one of those graphs corresponds to replacing the intervals, arcs or interval filaments associated with $u$ and $v$ in $\mathcal{I}$ by their union. Adding a true twin to a vertex $v$ such a graph corresponds to duplicating the interval, arc, interval filament associated with $v$ in $\mathcal{I}$. For this reason, they are replicable and induced minor closed.

**k-hole-free graphs.** The induced minor closeness follows from their definition and Lemma 1.4.

**Chordal graphs.** It is the special case $k=4$ of the previous one.

**Asteroidal triple-free.** The fact that asteroidal triple-free graphs are replicable follows from the fact their minimal forbidden induced subgraphs do not contain any true twin. Moreover, suppose that contracting an edge $uv$ of a graph $G$ yields an asteroidal triple, if the image $w_{uv}$ of $uv$ in $G/uv$ belongs to the triple then, replacing $w_{uv}$ by $u$ or $v$ yields another asteroidal triple (up to the addition of the other vertex to the corresponding path if necessary). $\square$

Given a cost function $c$ on the vertices of $G$, let $\tilde{c}_u = c_u$, for all $u \in V$, and $\tilde{c}_{uv} = c_u + c_v$, for all $uv \in E$. Then finding a maximum $c$-weighted co-2-plex in $G$ is equivalent to finding a maximum $\tilde{c}$-weighted stable set in $u(G)$. This gives the following corollary by **Corollary 2.6** and the fact that maximum weighted stable set problem is polynomial on perfect graphs, circular arc, interval filament, weakly chordal and asteroidal triple-free graphs [19,20,22].

**Corollary 2.13.** *Finding a maximum weighted co-2-plex in a contraction perfect (resp. circular arc, interval filament, asteroidal triple-free) graph can be done in polynomial time.*

Finally, contraction perfect graphs yield a new class of graphs for which a maximum weighted induced matching can be found in polynomial time.

**Corollary 2.14.** *Finding a maximum weighted induced matching in a contraction perfect graph can be done in polynomial time.*

## Conclusion

We introduce a new class of perfect graphs: those which remain perfect under the contraction of any edge set, and we give several characterizations. We show how this family of graph naturally appears when studying polynomial cases for the maximum weighted co-2-plex and induced matching problems when considering the utter graph or the squared line graph. Moreover, we give sufficient conditions on a graph class to be closed by utter graph so that polynomial results for maximum weighted co-2-plex or induced matching could be deduced from new upcoming polynomial cases for the maximum weighted stable set problem.

For $k=2$, it remains an intriguing question whether a coloring of the utter graph can be used to get a minimal covering of the input graph with co-2-plexes. When $k>2$, another interesting question is whether some extension of utter graphs could capture co-$k$-plexes as familiar combinatorial objects, like stable sets in utter graphs do for co-2-plexes. From a polyhedral point of view, the equivalence between co-2-plexes of a graph and stable sets of its utter graph will give extended formulations for the co-2-plex polytope from the stable set polytope.

Contraction perfect graphs being a new subclass of perfect graphs, one may also be interested in combinatorial algorithms to find a maximum clique/stable set or a minimum coloring on such graphs. Since, unlike for perfect graphs, the complement of a contraction perfect graph is not necessarily contraction perfect, finding a maximum clique or a stable set may lead to distinct studies.

## Acknowledgments

We thank Daria Pchelina for her contribution to Lemma 1.3. We also thank an anonymous referee for his precious remarks, reports and particularly for highlighting the links with Roussel and Rubio's lemma, Artemis graphs, and Grenoble graphs.

## Data availability

No data was used for the research described in the article.

## References

[1] B. Balasundaram, S. Butenko, I. Hicks, Clique relaxations in social network analysis: The maximum $k$-plex problem, Oper. Res. 59 (1) (2011) 133–142.

[2] M.E. Bertschi, Perfectly contractile graphs, J. Combin. Theory Ser. B 50 (2) (1990) 222–230.

[3] D. Bienstock, On the complexity of testing for odd holes and induced odd paths, Discrete Math. 90 (1) (1991) 85–92.

[4] K. Cameron, Induced matchings, Discrete Appl. Math. 24 (1) (1989) 97–102.

[5] K. Cameron, Induced matchings in intersection graphs, Discrete Math. 278 (1) (2004) 1–9.

[6] K. Cameron, R. Sritharan, Y. Tang, Finding a maximum induced matching in weakly chordal graphs, Discrete Math. 266 (1) (2003) 133–142.
[7] L. Chang, M. Xu, D. Strash, Efficient maximum k-plex computation over large sparse graphs, Proc. VLDB Endow. 16 (2) (2022) 127–139.

[8] J. Chaudhary, M. Zehavi, P-Matchings Parameterized by Treewidth, Springer Nature Switzerland, Cham, 2023, pp. 217–231.

[9] P. Chen, H. Wan, S. Cai, J. Li, H. Chen, Local search with dynamic-threshold configuration checking and incremental neighborhood updating for maximum k-plex problem, Proc. AAAI Conf. Artif. Intell. 34 (03) (2020) 2343–2350.

[10] P. Chen, H. Wan, S. Cai, W. Luo, J. Li, Combining reinforcement learning and configuration checking for maximum k-plex problem, 2019, ArXiv.

[11] M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas, The strong perfect graph theorem, Ann. Math. 164 (2006) 51–229.

[12] M. Chudnovsky, A. Scott, P. Seymour, S. Spirkl, Detecting an odd hole, J. ACM 67 (5) (2019) 1–12.

[13] M. Chudnovsky, P. Seymour, Even pairs in Berge graphs, J. Combin. Theory Ser. B 99 (2) (2009) 370–377.

[14] B. Courcelle, The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Inform. Comput. 85 (1) (1990) 12–75.

[15] Q. Dai, R.-H. Li, H. Qin, M. Liao, G. Wang, Scaling up maximal K-plex enumeration, in: 31st ACM International Conference on Information & Knowledge Management, CIKM '22, Association for Computing Machinery, New York, NY, USA, 2022, pp. 345–354.

[16] H. Everett, C.M. de Figueiredo, C. Linhares-Sales, F. Maffray, O. Porto, B.A. Reed, Path parity and perfection, Discrete Math. 165–166 (1997) 233–252, Graphs and Combinatorics.

[17] J. Fonlupt, J.-P. Uhry, Transformations which preserve perfectness and H-perfectness of graphs, in: A. Bachem, M. Grötschel, B. Korte (Eds.), Bonn Workshop on Combinatorial Optimization, in: North-Holland Mathematics Studies, vol. 66, North-Holland, 1982, pp. 83–95.

[18] F. Gavril, Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph, SIAM J. Comput. 1 (2) (1972) 180–187.

[19] F. Gavril, Algorithms on circular-arc graphs, Networks 4 (4) (1974) 357–369.

[20] F. Gavril, 3D-interval-filament graphs, Discrete Appl. Math. 155 (18) (2007) 2625–2636.

[21] M.C. Golumbic, Trivially perfect graphs, Discrete Math. 24 (1) (1978) 105–107.

[22] M. Grötschel, L. Lovász, A. Schrijver, Polynomial algorithms for perfect graphs, in: C. Berge, V. Chvátal (Eds.), in: North-Holland Mathematics Studies, vol. 88, 1984, pp. 325–356.

[23] Y. Huang, C. Shen, Learning computation bounds for branch-and-bound algorithms to k-plex extraction, 2022, CoRR abs/2208.05763.

[24] S. Jabbour, N. Mhadhibi, B. Raddaoui, L. Sais, A declarative framework for maximal k-plex enumeration problems, in: Adaptive Agents and Multi-Agent Systems, 2022.

[25] H. Jiang, D. Zhu, Z. Xie, S. Yao, Z.-H. Fu, A new upper bound based on vertex partitioning for the maximum K-plex problem, in: Z.-H. Zhou (Ed.), Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, WangAI-21, 2021, pp. 1689–1696.

[26] Y. Jin, J.H. Drake, K. He, U. Benlic, Reinforcement learning based coarse-to-fine search for the maximum k-plex problem, Appl. Soft Comput. 131 (2022) 109758.

[27] X. Liu, G. Cornuéjols, K. Vušković, A polynomial algorithm for recognizing perfect graphs, in: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, Oct 2003, IEEE Computer Society, Los Alamitos, CA, USA, 2003, p. 20.

[28] F. Maffray, N. Trotignon, A class of perfectly contractile graphs, J. Combin. Theory Ser. B 96 (1) (2006) 1–19.

[29] B. McClosky, I. Hicks, The Co-2-plex polytope and integral systems, SIAM J. Discret. Math. 23 (2009) 1135–1148.

[30] B. McClosky, I. Hicks, Combinatorial algorithms for the maximum k-plex problem, J. Comb. Optim. 23 (2012) 29–49.

[31] H. Meyniel, A new property of critical imperfect graphs and some consequences, European J. Combin. 8 (3) (1987) 313–316.

[32] H. Moser, R. Niedermeier, M. Sorge, Exact combinatorial algorithms and experiments for finding maximum k-plexes, J. Comb. Optim. (2012).

[33] H. Moser, S. Sikdar, The parameterized complexity of the induced matching problem, Discrete Appl. Math. 157 (4) (2009) 715–727.

[34] Y. Okubo, M. Matsudaira, M. Haraguchi, Detecting maximum k-plex with iterative proper l-plex search, Discov. Sci. (2014) 240–251.

[35] W. Pullan, Local search for the maximum k-plex problem, J. Heuristics 27 (3) (2021) 303–324.

[36] F. Roussel, P. Rubio, About skew partitions in minimal imperfect graphs, J. Combin. Theory Ser. B 83 (2) (2001) 171–190.

[37] S. Seidman, B. Foster, A graph-theoretic generalization of the clique concept, J. Math. Sociol. 6 (1978) 139–154.

[38] P.I. Stetsyuk, O. Khomiak, Y. Blokhin, A.A. Suprun, Optimization problems for the maximum k-plex, Cybernet. Systems Anal. 58 (2022) 530–541.

[39] N. Trotignon, K. Vušković, On Roussel-Rubio-type lemmas and their consequences, Discrete Math. 311 (8) (2011) 684–687.

[40] Z. Wang, Q. Chen, B. Hou, B. Suo, Z. Li, W. Pan, Z.G. Ives, Parallelizing maximal clique and k-plex enumeration over graph data, J. Parallel Distrib. Comput. 106 (2017a) 79–91.

[41] Y. Wang, X. Jian, Z. Yang, J. Li, Query optimal k-plex based community in graphs, Data Sci. Eng. 2 (4) (2017b) 257–273.

[42] K. Wu, J. Gao, R. Chen, X. Cui, Vertex selection heuristics in branch-and-bound algorithms for the maximum k-plex problem, Int. J. Artif. Intell. Tools 28 (05) (2019) 1950015.

[43] J. Zheng, M. Jin, Y. Jin, K. He, Relaxed graph color bound for the maximum k-plex problem, 2023, CoRR abs/2301.07300.

[44] Y. Zhou, S. Hu, M. Xiao, Z.-H. Fu, Improving maximum k-plex solver via second-order reduction and graph color bounding, Proc. AAAI Conf. Artif. Intell. 35 (14) (2021) 12453–12460.