# On the Computational Complexity of the
Bipartizing Matching Problem111This study was financed in part by the
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES)
Finance Code 001, by the Conselho Nacional de Desenvolvimento Científico e
Tecnológico - Brasil (CNPq) - CNPq/DAAD2015SWE/290021/2015-4, and FAPERJ.
A conference version appeared in the Proc. of the 12th Annual International
Conference on Combinatorial Optimization and Applications (COCOA), Volume
11346, pages 198–213, Atlanta, USA, December 2018.

Carlos V.G.C. Lima1,†, Dieter Rautenbach2,†, Uéverton S. Souza3,†,
and Jayme L. Szwarcfiter4 Email addresses<EMAIL_ADDRESS>(Lima),
<EMAIL_ADDRESS>(Rautenbach<EMAIL_ADDRESS>(Souza), and
<EMAIL_ADDRESS>(Szwarcfiter)

###### Abstract

We study the problem of determining whether a given graph $G=(V,E)$ admits a
matching $M$ whose removal destroys all odd cycles of $G$ (or equivalently
whether $G-M$ is bipartite). This problem is equivalent to determine whether
$G$ admits a $(2,1)$-coloring, which is a $2$-coloring of $V(G)$ such that
each color class induces a graph of maximum degree at most $1$. We determine a
dichotomy related to the NP-completeness of this problem, where we show that
it is NP-complete even for $3$-colorable planar graphs of maximum degree $4$,
while it is known that the problem can be solved in polynomial time for graphs
of maximum degree at most $3$. In addition we present polynomial-time
algorithms for some graph classes, including graphs in which every odd cycle
is a triangle, graphs of small dominating sets, and $P_{5}$-free graphs.
Additionally, we show that the problem is fixed parameter tractable when
parameterized by the clique-width, which implies polynomial-time solution for
many interesting graph classes, such as distance-hereditary, outerplanar, and
chordal graphs. Finally, an $O\left(2^{O\left(vc(G)\right)}\cdot
n\right)$-time algorithm and a kernel of at most $2\cdot nd(G)$ vertices are
presented, where $vc(G)$ and $nd(G)$ are the vertex cover number and the
neighborhood diversity of $G$, respectively.

Keywords: Graph modification problems $\cdot$ Edge bipartization $\cdot$
Defective coloring $\cdot$ Planar graphs $\cdot$ NP-completeness $\cdot$
Parameterized complexity

1 Departamento de Ciência da Computação, Universidade Federal de Minas Gerais,
Belo Horizonte, Brazil.
2 Institute of Optimization and Operations Research, Ulm University, Ulm,
Germany.
3 Instituto de Computação, Universidade Federal Fluminense, Niterói, Brazil.
4 PESC, COPPE, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil.

##  1 Introduction

Given a graph $G=(V,E)$ and a graph property $\Pi$, the $\Pi$ edge-deletion
problem consists in determining the minimum number of edges required to be
removed in order to obtain a graph satisfying $\Pi$ [14]. Given an integer
$k\geq 0$, the $\Pi$ edge-deletion decision problem asks for a set $F\subseteq
E(G)$ with $|F|\leq k$, such that the obtained graph by the removal of $F$
satisfies $\Pi$. Both versions have received widely attention on the study of
their computational complexity, where we can cite [47, 48, 14, 42, 3, 32, 35,
39]. They are particular cases of the general branch of graph editing
problems. In such problems some editing operations on the vertices or edges
are allowed in order to obtain a new graph satisfying the desired property.
They include vertex and edge additions and deletions, as in the problem
studied in this paper, flipping and contraction of edges. Examples of
applications and variations of graph modification problems can be found, for
example, in [17].

When the obtained graph is required to be bipartite, the corresponding edge
(resp. vertex) deletion problem is called edge (resp. vertex) bipartization
[16, 1, 30] or edge (resp. vertex) frustration [49, 31].

Choi et al. [16] showed that edge bipartization is NP-complete even for cubic
graphs. Furmańczyk et al. [30] considered vertex bipartization of cubic graphs
by removing an independent set. This problem has also been considered by
Bonamy et al. [9], where it is called Independent Odd Cycle Transversal. A
generalization of this problem is given by Agrawal et al. [2], which
generalizes cycle hitting problems. Given a graph $G$, a subgraph $H$ of $G$,
and a positive integer $k$, the goal is to decide whether there exists a
vertex subset $S$ of $G$ that intersects all desired cycles and $S$ is an
independent set in $H$. They called this problem as Conflict Free Feedback
Vertex Set and studied it from the view-point of parameterized complexity.

In this paper we study the similar version for the edge deletion decision
problem for odd cycles. That is, the problem of determining whether a finite,
simple, and undirected graph $G$ admits a removal of an edge set that is a
matching in $G$ in order to obtain a bipartite graph. Formally, for a set
$S\subseteq E(G)$, let $G-S$ be the graph with vertex set $V(G)$ and edge set
$E(G)\setminus S$. We say that a matching $M\subseteq E(G)$ is a bipartizing
matching of $G$ if $G-M$ is bipartite. Denoting by $\mathcal{BM}$ the family
of all graphs admitting a bipartizing matching, we deal with the computational
complexity of the following decision problem.

Bipartizing Matching (BM)
Input: A finite, simple, and undirected graph $G$.
Question: Does $G\in\mathcal{BM}$?

A more restricted version was considered by Schaefer [45], which asked whether
a given graph $G$ admits a $2$-coloring of the vertices such that each vertex
has _exactly_ one neighbor with same color as itself. We can see that the
removal of the set of edges whose endvertices have same color, which is a
perfect matching of $G$, generates a bipartite graph. He proved that this
problem is NP-complete even for planar cubic graphs.

With respect to the minimization version, where the set of removed edges is
not required to be a matching, the edge-deletion decision problem in order to
obtain a bipartite graph is analogous to the Simple Max Cut problem, which was
proved to be NP-complete by Garey et al. [32]. Yannakakis [47] proved its NP-
completeness even for cubic graphs.

BM can also be seen as a defective coloring [24]. A $(k,d)$-coloring of a
graph $G$ is a $k$-coloring of $V(G)$ such that each vertex has at most $d$
neighbors with same color as itself. Defective colorings were introduced
independently by Andrews and Jacobson [4], Harary and Jones [36], and Cowen et
al. [23], which received wide attention in the literature [5, 29, 10, 24, 6].
We can see that any proper coloring is a $(k,0)$-coloring, for some $k\geq 1$.
Moreover, a graph belongs to $\mathcal{BM}$ if and only if it admits a
$(2,1)$-coloring.

Lovász [40] proved that if a graph $G$ satisfies
$(d_{1}+1)+(d_{2}+1)+\dots+(d_{k}+1)\geq\Delta(G)+1$, then $V(G)$ can be
partitioned into $V_{1},\dotsc,V_{k}$, such that each induced subgraph
$G[V_{i}]$ has maximum degree at most $d_{i}$, $1\leq i\leq k$, where
$\Delta(G)$ is the maximum degree of $G$. A proof of this result can be found
in [24]. This result implies that all subcubic graphs $G$, graphs satisfying
$\Delta(G)\leq 3$, are $(2,1)$-colorable.

Cowen et al. [24] proved that it is NP-complete to determine whether a given
graph is $(2,1)$-colorable, even for graphs of maximum degree 4 and even for
planar graphs of maximum degree 5. Angelini et al. [5] presented a linear-time
algorithm which determines that partial $2$-trees, a subclass of planar
graphs, are $(2,1)$-colorable. We emphasize that a $k$-tree has treewidth at
most $k$, for any $k\geq 1$.

Eaton and Hull [29] proved that all triangle-free outerplanar graphs are also
$(2,1)$-colorable. Borodin et al. [10] studied graphs with respect to a
sparseness parameter, the average degree

$mad(G)=\max\left\\{\frac{2|E(H)|}{|V(H)|}\textnormal{, for all }H\subseteq
G\right\\}.$

They proved that every graph $G$ with $mad(G)\leq\frac{14}{5}$ is
$(2,1)$-colorable, where this bound is sharp. Moreover, they defined the
parameter $\rho(G)=\min_{S\subseteq V(G)}\rho_{G}(S)$, such that
$\rho_{G}(S)=7|S|-5|E(G[S])|$. They showed that $G$ is $(2,1)$-colorable if
$\rho(G)\geq 0$. By the Euler’s formula, a planar graph $G$ with girth $g$,
the size of a smallest cycle, has $mad(G)<\frac{2g}{g-2}$. Hence if $G$ has
girth at least $7$, then it is $(2,1)$-colorable.

The similar problem where the opposite condition on the degrees is considered
for each part of the bipartition, that is, each part induces a subgraph of
minimum degree at least a given positive integer, is studied by Bang-Jensen
and Bessy [7].

Another variations are given in [39, 43], where the resulting graph by the
removal of a matching is required to be a forest, eliminating even the even
cycles of the input graph. As these works, our study in this paper consists in
trying to find a bipartizing matching instead of trying improperly color the
graph.

###  1.1 Our Results

####  1.1.1 NP-completeness

In this paper we extend the results of Cowen et al. [24]. As we said before,
they proved the NP-completeness of determining whether a given graph is
$(2,1)$-colorable, even for graphs of maximum degree 4 and for planar graphs
of maximum degree 5. However, the complexity of $(2,1)$-color for planar
graphs of maximum degree 4 has been left open, which is our first
contribution.

######  Theorem 1.

BM is NP-complete for $3$-colorable planar graphs of maximum degree 4.

More precisely, Lovász [40] proved the following theorem that appears many
times in the literature and whose proof can be found in [24].

######  Theorem 2 ([40]).

For any integer $k>0$, any graph of maximum degree $\Delta$ admits a
$\left(k,\lfloor\Delta/k\rfloor\right)$-coloring.

While Theorem 2 ensures that all graphs of maximum degree $\Delta=2d+1$ admit
a $(2,d)$-coloring, Cowen et al. [24] proved that deciding whether a given
graph of maximum degree $2(d+1)$ is $(2,d)$-colorable is NP-complete.
Therefore they proposed the following question for the general case.

######  Question 1 ([24]).

In general, what is the complexity of deciding whether a given graph of
maximum degree $k(d+1)$ admits a $(k,d)$-coloring?

Angelini et al. [5] answered Question 1 for $(3,1)$-coloring, showing that it
is NP-complete for graphs of maximum degree 6. However, they were unable to
answer Question 1 restricted to planar graphs, that is, to give the complexity
of deciding whether a planar graph of maximum degree $6$ admits a
$(3,1)$-coloring, proving the NP-completeness for planar graphs of maximum
degree 7.

Cowen et al. [24] also proved that, for any integer $d>0$, deciding whether a
planar graph of maximum degree $4d+3$ is $(2,d)$-colorable is NP-complete.
Theorem 1 shows that this bound on the maximum degree is not tight.

Dorbec et al. [27] proved the NP-completeness of $(2,2)$-coloring for planar
graphs of maximum degree 4 and with no $C_{4}$, but restricted to the case of
bipartising the graph by the removal of 3-vertex star forests. Such defective
colorings, where the induced subgraphs by each part are required to be
forests, are known as (star, $k$)-coloring [5], when the size of each star is
not bounded, or $d$-star $k$-partition [27], in the case that each star has at
most $d$ vertices. We emphasize that such defective colorings are restricted
cases of $(k,d)$-colorings.

The family of cographs contains the single vertex $K_{1}$ and is closed with
respect to disjoint union and complementation. The cograph $k$-partition of a
graph $G$ is a $k$-coloring of $V(G)$ into color classes that are cographs.
Note that the cographs can have unbounded maximum degree in each color class
and the (star, $k$)-coloring and $d$-star $k$-partition are particular cases
of cograph $k$-partition. Gimbel and Nešetřil [33] proved that deciding
whether a planar graph of maximum degree at most 6 is cograph
$2$-partitionable is NP-complete. However, each component of the bipartition
can have a cograph of maximum degree greater than $2$.

In the proof of the upper bound $4d+3$ on the maximum degree, Cowen et al.
[24] considered a $d$-star $2$-partition of the graph, which also indicates
that this bound can be improved. Note that Theorem 2 establishes that all
graphs of maximum degree at most 5 are $(2,2)$-colorable. In this paper we
also prove the following theorem based on Theorem 1.

######  Theorem 3.

Deciding whether a planar graph of maximum degree $6$ admits a
$(2,2)$-coloring, that is not necessarily a cograph 2-partition, is NP-
complete.

Theorem 3 is less restrictive than the result of Gimbel and Nešetřil [33],
being the best possible with respect to the maximum degree by Theorem 2. In
the same way, we use Theorem 3 in order to prove a similar result for
$(2,3)$-color planar graphs.

######  Corollary 4.

It is NP-complete to decide whether a planar graph of maximum degree $8$ is
$(2,3)$-colorable.

Theorems 1, 2, 3, and Corollary 4 show a dichotomy with respect to the
computational complexity of $(2,d)$-color planar graphs of bounded maximum
degree for $d\leq 3$. More precisely, they suggest that the bound of $4d+3$ on
the maximum degree to $(2,d)$-color planar graphs can be improved.
Unfortunately, our construction on the proofs cannot be extended for $d\geq 4$
in a tight way, but is still better than the upper bound $4d+3$ for $d\leq 7$.
Therefore, in order to generalize Question 1 for planar graphs, we propose an
initial one restricted to $(2,d)$-color planar graphs.

######  Question 2.

What is the minimum integer $\Delta^{*}$, $2d+2\leq\Delta^{*}\leq 4d+3$, such
that deciding whether a given planar graph of maximum degree $\Delta^{*}$
admits a $(2,d)$-coloring is NP-complete?

####  1.1.2 Positive Results

On the positive side, we present polynomial-time algorithms for on several
graph classes.

######  Theorem 5.

BM can be solved in polynomial time for the following graph classes:

  * (a)

graphs having bounded dominating set;

  * (b)

$P_{5}$-free graphs.

  * (c)

graphs in which every odd-cycle subgraph is a triangle;

We also study parameterized complexity aspects. Using Courcelle’s meta-
theorems [18, 22, 19] we prove that BM is fixed-parameter tractable when
parameterized by the clique-width, which improves the previous result of
Angelini et al. [5].

######  Theorem 6.

BM is FPT when parameterized by the clique-width.

By Theorem 6 we can solve BM for several interesting graph classes in
polynomial time, as for example distance-hereditary, series-parallel, control-
flow, and some subclasses of planar graphs such as outerplanar, Halin, and
Apollonian networks [11, 34, 8, 46]. The same follows for ($P_{6}$, claw)-free
and (claw, co-claw)-free graphs [13, 12]. Moreover, since clique-width
generalizes several graph parameters [38], it follows that BM is in FPT when
parameterized by the following parameters: neighborhood diversity; treewidth;
pathwidth; feedback vertex set; and vertex cover. In addition, it also follows
that

######  Corollary 7.

BM is polynomial-time solvable for chordal graphs.

We also show an exact $2^{O(vc(G))}\cdot n$ algorithm, where $vc(G)$ is the
vertex cover number of $G$. Finally, for a generalization of BM , we show a
kernel with at most $2\cdot nd(G)$ vertices when a more general problem is
parameterized by neighborhood diversity number, $nd(G)$.

####  1.1.3 Organization of the Paper

We summarize our results as follows. In Section 2 we present some basic
definitions and notation used throughout the paper and some initial properties
of graphs in $\mathcal{BM}$. In Section 3 we present the proof of Theorem 1.
In Section 4 we present the proofs of the statements in Theorems 5. In Section
5 we consider the parameterized complexity aspects and present the proof of
Theorem 6. In Section 6 we consider the complexity of $(2,d)$-color planar
graphs of bounded degree, for $d\geq 2$, and present the proofs of Theorem 3
and Corollary 4. Finally in Section 7 we present the conclusions.

##  2 Preliminaries

###  2.1 Basic Definitions and First Remarks

Now we present some basic definitions, notations, and some initial remarks. We
use standard notation and definitions of graph theory, where we consider only
simple and undirected graphs. For more details on graph terminology and
notation, see [26].

Given a graph $G=(V,E)$, we denote by $n(G)$ and $m(G)$ the number of vertices
and edges of $G$, respectively. For a vertex $v\in V(G)$, let $N_{G}(v)$ be
the neighborhood of $v$ in $G$ and $N_{G}[v]=\\{v\\}\cup N_{G}(v)$ its closed
neighborhood in $G$. The degree of $v\in V(G)$, $|N_{G}(v)|$, is denoted as
$d_{G}(v)$. The subscripts can change for a subgraph $H$ of $G$ when
necessary.

Given a set $S\in V(G)$, let $H=G[S]$ be the induced subgraph of $G$ by $S$,
such that $V(H)=S$ and $uv\in E(H)$ if and only if $uv\in E(G)$ and $u,v\in
S$. We also say that $S$ induces $H$ and that $H$ is the graph induced by $S$.

Let $P_{n}=v_{1}v_{2}\dots v_{n}$ and $C_{n}=v_{1}v_{2}\dots v_{n}v_{1}$ be
the induced path and induced cycle of order $n$, respectively. Furthermore, we
denote by $K_{n}$ and $K_{n,m}$ the complete graph of order $n$ and the
complete bipartite graph with parts of order $n$ and $m$, respectively. A
diamond is the graph obtained by removing one edge from the $K_{4}$.

A universal vertex $v$ of a graph $G$ is one adjacent to all vertices in
$V(G)\setminus\\{v\\}$. For an integer $k\geq 3$, let $W_{k}$ denote the wheel
graph of order $k+1$, that is, the graph obtained by connecting a universal
vertex, called central, to all the vertices of an induced cycle $C_{k}$. The
$W_{4}$ and $W_{5}$ are depicted in Figures 1(a) and 1(b), respectively.

We say that a graph $G$ is a $k$-pool if it is composed by $k$-edge disjoint
triangles whose union of all the vertices of their bases induces a $C_{k}$.
Formally, a $k$-pool is obtained from an induced cycle $C_{2k}=v_{1}v_{2}\dots
v_{2k}v_{1}$, $k\geq 3$, such that the vertices with index odd induce the
internal cycle $p_{1}p_{2}\dots p_{k}p_{1}$ of the $k$-pool, where
$p_{i}=v_{2i-1}$, $1\leq i\leq k$. The vertex with index even $b_{i}=v_{2i}$,
$1\leq i\leq k$, is called the $i$-th-border of the $k$-pool. For $G$ a
$k$-pool, if $k$ is odd, then we say that $G$ is an odd $k$-pool, otherwise we
say that it is an even $k$-pool. The $3$-pool and $5$-pool are depicted in
Figures 1(c) and 1(d), respectively.

(a) $W_{4}$.

(b) $W_{5}$.

(c) $3$-pool.

(d) 5-pool.

(e) Two diamonds sharing a $3$-degree vertex.

Figure 1: Some examples of forbidden subgraphs.

Since $\mathcal{BM}$ is closed under taking subgraphs, we can search for
families of minimal forbidden subgraphs, that is, graphs that cannot be in
$\mathcal{BM}$. Figure 1 depicts some examples of them, while Lemma 8 collects
some properties of graphs in $\mathcal{BM}$.

######  Lemma 8.

For a graph $G\in\mathcal{BM}$ and a bipartizing matching $M$ of $G$, the
following statements hold:

  * (i)

For every diamond $D$ of $G$, $M$ matches both vertices of degree 3 of $D$.

  * (ii)

For every $v\in V(G)$, $G[N_{G}(v)]$ does not contain two disjoint $P_{3}$.

  * (iii)

$G$ does not contain a $W_{k}$ as a subgraph, for all $k\geq 4$.

  * (iv)

$G$ does not contain an odd $k$-pool as subgraph, for all odd $k\geq 3$.

###### Proof.

(i) Let $D$ be a diamond subgraph of $G$, such that
$V(D)=\\{u,v_{1},v_{2},v_{3}\\}$ and $d_{D}(u)=d_{D}(v_{2})=3$. We can see
that $M\cap E(D)$ must be one of the following sets:
$\\{uv_{1},v_{2}v_{3}\\}$, $\\{v_{1}v_{2},uv_{3}\\}$, $\\{uv_{2}\\}$. In each
one, $u$ and $v_{2}$ are matched by $M$.

(ii) Suppose for a contradiction that $v\in V(G)$ is such that $G[N_{G}(v)]$
contains two disjoint $P_{3}$: $P$ and $P^{\prime}$. This implies that
$G[\\{v\\}\cup P]$ and $G[\\{v\\}\cup P^{\prime}]$ are diamonds sharing a
vertex of degree three. Then, by Statement (i) it follows that $M$ contains
two incident edges, one for each diamond, a contradiction.

(iii) Suppose for a contradiction that $G$ contains a subgraph $H$ isomorphic
to $W_{k}$, $k\geq 4$, where $u$ is universal in $H$. If $k\geq 7$, it follows
that $u$ has two disjoint $P_{3}$ in its neighborhood, a contradiction by
Statement (ii). Then $k\leq 6$ and it can be easily verified that $W_{4}$ and
$W_{5}$ are not in $\mathcal{BM}$.

(iv) Suppose for a contradiction that $G$ contains a subgraph $H$ isomorphic
to an odd $k$-pool, for an odd $k\geq 3$. Let $C=p_{1}p_{2}\ldots p_{k}p_{1}$
be its internal cycle and let $B=\\{b_{1},b_{2},\dotsc,b_{k}\\}$ be the set of
vertices of the borders of $H$, such that
$\\{p_{i}b_{i},p_{i+1}b_{i}\\}\subset E(H)$, for all $1\leq i\leq k$ modulo
$k$. Clearly $M$ must contain some edge of $C$ and one edge of every triangle
$p_{i}b_{i}p_{i+1}p_{i}$. W.l.o.g., consider $p_{1}p_{2}\in M\cap E(C)$. This
implies that $M$ contains no edge in
$\\{p_{2}b_{2},p_{2}p_{3},p_{1}b_{k},p_{1}p_{k}\\}$. Therefore, $p_{k}b_{k}$
and $p_{3}b_{2}$ must be in $M$, which forbids two more edges from the
triangles $p_{k-1}b_{k-1}p_{k}p_{k-1}$ and $p_{3}b_{3}p_{4}p_{3}$. Continuing
this process, it follows that $c_{\left\lfloor\frac{k+3}{2}\right\rfloor}$,
which is at the same distance of $p_{1}$ and $p_{2}$ in $C$, must contain two
incident edges in $M$, a contradiction. ∎

Clearly every graph in $\mathcal{BM}$ admits a proper $4$-coloring. Hence
every graph in $\mathcal{BM}$ is $K_{5}$-free, implying that all graphs in
$\mathcal{BM}$ have maximum clique bounded by 4. More precisely, every graph
in $\mathcal{BM}$ is $W_{5}$-free, as in Lemma 8, which implies that even some
properly $3$-colorable graphs do not admit a decycling matching.

###  2.2 Basics on Parameterized Complexity

For a basic background on parameterized complexity, we refer to [25, 28], and
only some definitions are given here. A _parameterized problem_ is a language
$L\subseteq\Sigma^{*}\times\mathbb{N}$. For an instance
$I=(x,k)\in\Sigma^{*}\times\mathbb{N}$, $k$ is called the _parameter_. A
parameterized problem is _fixed-parameter tractable_ (FPT) if there exists an
algorithm $\mathsf{A}$, a computable function $f$, and a constant $c$ such
that given an instance $I=(x,k)$, $\mathsf{A}$ (called an FPT _algorithm_)
correctly decides whether $I\in L$ in time bounded by $f(k)\cdot|I|^{c}$.

A fundamental concept in parameterized complexity is that of _kernelization_.
A kernelization algorithm, or just _kernel_ , for a parameterized problem
$\Pi$ takes an instance $(x,k)$ of the problem and, in time polynomial in
$|x|+k$, outputs an instance $(x^{\prime},k^{\prime})$ such that
$|x^{\prime}|,k^{\prime}\leqslant g(k)$ for some function $g$, and
$(x,k)\in\Pi$ if and only if $(x^{\prime},k^{\prime})\in\Pi$. The function $g$
is called the _size_ of the kernel and may be viewed as a measure of the
“compressibility” of a problem using polynomial-time preprocessing rules. A
kernel is called _polynomial_ (resp. _linear_) if $g(k)$ is a polynomial
(resp. linear) function in $k$. It is nowadays a well-known result in the area
that a decidable problem is in FPT if and only if it has a kernelization
algorithm. However, the kernel that one obtains in this way is typically of
size at least exponential in the parameter. A natural problem in this context
is to find polynomial or linear kernels for problems that are in FPT.

##  3 NP-Completeness

Let $F$ be a Boolean formula in $3$-CNF such that
$\textbf{X}=\\{X_{1},X_{2},\dotsc,X_{n}\\}$ is the variable set and
$\textbf{C}=\\{C_{1},C_{2},\dotsc,C_{m}\\}$ is the clause set of $F$. We
represent the positive and negative literals of $X_{i}$ as $x_{i}$ and
$\overline{x_{i}}$, respectively. The associated graph $G_{F}=(V,E)$ of $F$ is
the bipartite graph such that there exists a vertex for every variable and
clause of $F$, where $(\textbf{X},\textbf{C})$ is the bipartition of
$V(G_{F})$, and there exists an edge $X_{i}C_{j}\in E(G_{F})$ if and only if
$C_{j}$ contains either $x_{i}$ or $\overline{x_{i}}$. We say that $F$ is a
planar formula if $G_{F}$ is planar.

In order to prove Theorem 1, we first present a polynomial-time reduction from
the well known problem Positive Planar 1-In-3-SAT [41] to Planar 1-In-3-SAT3,
defined as follows.

Positive Planar 1-In-3-SAT [41]
Input: A planar formula $F$ in $3$-CNF with no negative literals.
Question: Is there a truth assignment to the variables of $F$, in which each
clause has exactly one literal assigned true?

Planar 1-In-3-SAT3
Input: A planar formula $F$ in CNF, where each clause has either $2$ or $3$
literals and each variable occurs at most $3$ times. Moreover, each positive
literal occurs at most twice, while every negative literal occurs at most once
in $F$.
Question: Is there a truth assignment to the variables of $F$ in which each
clause has exactly one true literal?

######  Theorem 9.

Planar 1-In-3-SAT3 is NP-complete.

###### Proof.

Let $F$ be a planar formula in $3$-CNF such that
$\textbf{X}=\\{X_{1},X_{2},\dotsc,X_{n}\\}$ is the variable set and
$\textbf{C}=\\{C_{1},C_{2},\dotsc,C_{m}\\}$ is the clause set of $F$. Since
verifying whether a graph is planar can be done in linear time [37], as well
as whether a formula in $3$-CNF has a truth assignment, the problem is in NP.

We construct a formula $F^{\prime}$ from $F$ as follows. If $X_{i}$ is such
that $d_{G_{F}}(X_{i})=k\geq 3$, then we create $k$ new variables $X_{i}^{z}$
replacing the $j^{th}$ ($1\leq j\leq k$) occurrence of $X_{i}$ by a variable
$X_{i}^{j}$, where a literal $x_{i}$ (resp. $\overline{x_{i}}$) is replaced by
a literal $x_{i}^{j}$ $(\textnormal{resp. }\overline{x_{i}^{j}})$. In
addition, we create $k$ new clauses
$C_{i}^{j}=\left(x_{i}^{j},\overline{x_{i}^{j+1}}\right)$, for
$j\in\\{1,\dotsc,k-1\\}$, and
$C_{i}^{k}=\left(x_{i}^{k},\overline{x_{i}^{1}}\right)$.

Let $S$ be the set of all vertices $X_{i}\in V(G_{F}[\textbf{X}])$ with
$d_{G_{F}}(X_{i})=k\geq 3$. For such a vertex $X_{i}\in S$, let
$X^{\prime}_{i}=\\{X_{i}^{1},\dotsc,X_{i}^{k}\\}$ and
$C^{\prime}_{i}=\\{C_{i}^{1},\dotsc,C_{i}^{k}\\}$.

Note that, the associated graph $G_{F^{\prime}}$ can be obtained from $G_{F}$
by replacing the corresponding vertex of $X_{i}\in S$ by a cycle of length
$2d_{G_{F}}(X_{i})$ induced by the corresponding vertices of the new clauses
in $C^{\prime}_{i}$ and the new variables in $X^{\prime}_{i}$. In addition,
for each $X_{i}\in S$ and $C_{j}\in N_{G_{F}}(X_{i})$, an edge
$X_{i}^{t}C_{j}$ is added in $E(G_{F^{\prime}})$, such that every
corresponding vertex $X_{i}^{t}\in X^{\prime}_{i}$ has exactly one neighbor
$C_{j}\notin C^{\prime}_{i}$.

As we can see, every variable $X$ occurs at most $3$ times in the clauses of
$F^{\prime}$, since every variable $X_{i}$ with $d_{G_{F}}(X_{i})\geq 3$ is
replaced by $d_{G_{F}}(X_{i})$ new variables that are in exactly $3$ clauses
of $F^{\prime}$. By the construction, each literal occurs at most twice.
Moreover, if $F$ has no negative literals, then only the new variables have a
negative literal and each one occurs exactly once in $F^{\prime}$.

Consider a planar embedding $\Psi$ of $G_{F}$. We construct $G_{F^{\prime}}$
replacing each corresponding vertex $X_{i}\in S$ by a cycle of length
$2d_{G_{F}}(X_{i})$, as described above. After that, in order to preserve the
planarity, we can follow the planar embedding $\Psi$ to add a matching between
vertices corresponding to variables in such a cycle and vertices corresponding
to clauses $C_{j}\notin C^{\prime}_{i}$ and that $X_{i}\in C_{j}$. This
matching indicates in which clause of $C^{\prime}_{i}$ a given new variable
will replace $X_{i}$ in $F^{\prime}$. Thus, without loss of generality, if
$G_{F}$ is planar, then we can assume that $F^{\prime}$ is planar as well.

As we can observe, for any truth assignment of $F^{\prime}$, all $X_{i}^{t}\in
X_{i}$ (for a given variable $X_{i}$ of $F$) have the same value. Hence, any
clause of $F^{\prime}$ with exactly two literals has true and false values. At
this point, it is easy to see that $F$ has a 1-in-3 truth assignment if and
only if $F^{\prime}$ has a 1-in-3 truth assignment. ∎

Now we show the NP-completeness of BM. Let us call the graph depicted in
Figure 2(a) by head. We also call the vertex $v$ as the neck of the head.
Given a graph $G$, the next lemma shows that this structure is very useful to
ensure that some edges cannot be in any odd decycling matching of $G$.

(a) The head graph $H$.

(b) The bipartizing matching of $H$.

Figure 2: The head graph and its unique bipartizing matching.

######  Lemma 10.

An induced head $H$ with neck $v$ admits exactly one bipartizing matching $M$.
Moreover $v$ is matched by $M$.

###### Proof.

We can see that the thicker edges in Figure 2(b) compose a bipartizing
matching $M$ of $H$, where the color of the vertices indicates the part of
each one in $G-M$. Moreover $M$ satisfies the lemma.

Now let us suppose that $H$ admits another bipartizing matching $M^{\prime}$,
which does not match $v$. In this case, we get that $vh_{1}$ and $vh_{4}$ does
not belong to $M^{\prime}$, implying that $h_{1}h_{4}\in M^{\prime}$. By the
triangle $h_{1}h_{2}h_{5}$, it follows that $h_{2}h_{5}$ must be in
$M^{\prime}$. Hence the cycle $vh_{1}h_{2}h_{3}h_{4}v$ remains in
$G-M^{\prime}$, a contradiction.

Let $M^{\prime\prime}$ be a bipartizing matching that contains $vh_{4}$. In
this case, the edge $h_{1}h_{2}$ cannot be in $M^{\prime\prime}$, otherwise
the cycle $h_{1}h_{4}h_{3}h_{2}h_{5}h_{1}$ survives in $G-M^{\prime\prime}$.
In the same way, the edge $h_{1}h_{5}\notin M^{\prime\prime}$, otherwise the
cycle $h_{1}h_{2}h_{5}h_{3}h_{4}h_{1}$ is not destroyed by $M^{\prime\prime}$.
Therefore we get that $h_{2}h_{5}$ must be in $M^{\prime\prime}$, which
implies that the cycle $h_{1}h_{4}h_{3}h_{2}h_{5}h_{1}$ belongs to
$G-M^{\prime\prime}$, a contradiction. ∎

######  Lemma 11.

Let $G$ be an odd $k$-pool with internal cycle $C=p_{1}p_{2}\dots p_{k}p_{1}$.
Let $b$ be a border of $G$, where $N_{G}(b)=\\{p_{1},p_{k}\\}$. Then every
bipartizing matching $M$ of $G-b$ contains exactly one edge of $C$. Moreover,
$c_{1}c_{k}\notin M$ for such bipartizing matchings.

###### Proof.

Let $b_{i}$ be the $i$-th-border of $G$, such that
$N_{G}(b_{i})=\\{p_{i},p_{i+1}\\}$, $1\leq i\leq k-1$. Since $k$ is odd, every
bipartizing matching of $G-b$ must contain at least one edge of $C$.

First, suppose that $G-b$ has a bipartizing matching $M$ containing
$p_{1}p_{k}$. In this case, we get that the edges in
$\\{p_{1}p_{2},p_{1}b_{1},p_{k}p_{k-1},p_{k}b_{k-1}\\}$ cannot be in $M$. Thus
$M$ must contain edges $b_{1}p_{2}$ and $b_{k-1}p_{k-1}$. In the same way, we
can see that $M$ cannot contain the edges
$\\{p_{2}p_{3},p_{2}b_{2},p_{k-1}p_{k-2},$ $p_{k-1}b_{k-2}\\}$. Hence, it can
be seen that all edges incident to $p_{\frac{k+1}{2}}$ are forbidden to be in
$M$, which implies that the triangles containing $p_{\frac{k+1}{2}}$ have no
edge in $M$, a contradiction by the choice of $M$.

Let $p_{i}p_{i+1}$ be an edge of $C$ in a bipartizing matching $M$ of $G-b$,
with $i\neq k$. In a same fashion, the edges in
$\\{p_{i}p_{i-1},p_{i}b_{i-1},p_{i+1}p_{i+2},p_{i+1}b_{i+1}\\}$ cannot be in
$M$. Following this pattern, we can see that every edge $b_{j}p_{j+1}$ must be
in $M$, for every $j\in\\{1,\dotsc,k\\}\setminus\\{i\\}$. Since $M$ contains
only one edge of $C$ and one edge of every triangle of $G-b$, it follows that
$M$ is unique, for each edge $p_{i}p_{i+1}$, $i\neq k$. ∎

NP-Completeness for Planar Graphs of Maximum Degree 4.

We prove the NP-completeness by a reduction from Planar 1-In-3-SAT3. We first
prove it for $3$-colorable planar graphs of maximum degree 5. The circles with
an $H$ in the figures are induced head graphs, whose neck is the vertex
touching the circle.

(a) For clauses of size two.

(b) For clauses of size three.

(c) Variable gadget.

Figure 3: Figure 3(a) and 3(b) are the clause gadgets and Figure 3(c) is the
variable gadget in Theorem 12. Each pair of arrow edges connects $G_{X_{i}}$
to one clause gadget $G_{C}$ such that $X_{i}\in C$.

######  Theorem 12.

BM is NP-complete for $3$-colorable planar graphs $G$ of $\Delta(G)=5$.

###### Proof.

Let $F$ be an instance of Planar 1-In-3-SAT3, with
$X=\\{X_{1},X_{2},\dotsc,X_{n}\\}$ and $C=\\{C_{1},C_{2},\dotsc,$ $C_{m}\\}$
be the sets of variables and clauses of $F$, respectively. We construct a
planar graph $G=(V,E)$ of maximum degree $5$ as follows:

  * •

For each clause $C_{j}\in C$, we construct a gadget $G_{C_{j}}$ as depicted in
Fig. 3(a) and Fig. 3(b). Such gadgets are just a $5$-pool and a $7$-pool that
we remove a border vertex, for clauses of size $2$ and $3$, respectively.
Moreover, for the alternate edges of the internal cycle we subdivide them
twice and append a head to each such a new vertex. Finally, we add two
vertices $\ell_{j}(k,w)$ and $\ell_{j}(k,b)$, such that
$b_{j}^{2k-1}\ell_{j}(k,w)\in E(G)$ and $b_{j}^{2k}\ell_{j}(k,b)\in E(G)$, for
$k\in\\{1,2,3\\}$. We append a head to all such new vertices.

  * •

For each variable $X_{i}\in X$, we construct a gadget $G_{X_{i}}$ as depicted
in Figure 3(c). This gadget is a $7$-pool that we remove a border vertex.
Moreover, we subdivide twice the edges $p_{i}^{2}p_{i}^{3}$,
$p_{i}^{3}p_{i}^{4}$, $p_{i}^{4}p_{i}^{5}$, and $p_{i}^{6}p_{i}^{7}$,
appending a head to each new vertex. We rename each border vertex
$b_{i}^{2k-1}$ as $d_{i}(k,b)$, $k\in\\{1,3\\}$, and $b_{i}^{2k}$ as
$d_{i}(k,w)$, $k\in\\{1,2,3\\}$. Finally, a vertex $d_{i}(2,b)$ with a pendant
head and adjacent to $p_{i}^{4}$ is added.

  * •

The connection between clause and variable gadgets is as in Figure 3. Each
pair of arrow edges in a variable gadget $G_{X_{i}}$ corresponds to the same
pair in a clause gadget $G_{C_{j}}$, where $X_{i}\in C_{j}$. Precisely, if
$x_{i}\in C_{j}$, then we add the edges $\ell_{j}(k,b)d_{i}(k^{\prime},b)$ and
$\ell_{j}(k,w)d_{i}(k^{\prime},w)$, for some $k\in\\{1,2,3\\}$ and some
$k^{\prime}\in\\{1,2\\}$. Note that each $\ell_{j}(k,b)$ (and $\ell_{j}(k,w)$)
represents precisely one variable and it is connected to only one of
$d_{i}(k^{\prime},b)$ (and $d_{i}(k^{\prime},w)$) in $G_{X_{i}}$. However, if
$\overline{x_{i}}\in C_{j}$, then we add the edges $\ell_{j}(k,b)d_{i}(3,b)$
and $\ell_{j}(k,w)d_{i}(3,w)$, for some $k\in\\{1,2,3\\}$. Note that
$d_{i}(3,b)$ and $d_{i}(3,w)$ represent $\overline{x_{i}}$.

  * •

For a variable occurring exactly twice in $F$, just consider those connections
corresponding to literals of $X_{i}$ in the clauses of $F$, i.e., the pair
$d_{i}(3,b)$, $d_{i}(3,w)$ (resp. $d_{i}(2,b)$, $d_{i}(2,w)$) will be used to
connect to a clause gadget only if $\overline{x_{i}}$ occurs (resp. does not
occur) in $F$.

Let $G$ be the graph obtained from $F$ by the above construction. We can see
that $G$ has maximum degree $5$, where the only vertices with degree $5$ are
those $p_{i}^{4}$, for each variable gadget. Furthermore, it is clear that $G$
is $3$-colorable.

It remains to show that if $G_{F}$ is planar, then $G$ is planar. Consider a
planar embedding $\psi$ of $G_{F}$. We replace each vertex $v_{X_{i}}$ of
$G_{F}$ by a variable gadget $G_{X_{i}}$, as well as every vertex $v_{C_{j}}$
of $G_{F}$ by a clause gadget $G_{C_{j}}$. The clause gadgets correspond to
clauses of length two or three, which depends on the degree of $v_{C_{j}}$ in
$G_{F}$. Since the clause and variable gadgets are planar, we just need to
show that the connections among them keep the planarity. Given an edge
$v_{X_{i}}v_{C_{j}}\in E(G_{F})$, we connect $G_{X_{i}}$ and $G_{C_{j}}$ by
duplicating such an edge as parallel edges $\ell_{j}(k,w)d_{i}(k^{\prime},w)$
and $\ell_{j}(k,b)d_{i}(k^{\prime},b)$, for some $k\in\\{1,2,3\\}$ and some
$k^{\prime}\in\\{1,2\\}$, or $\ell_{j}(k,b)d_{i}(3,b)$ and
$\ell_{j}(k,w)d_{i}(3,w)$, for some $k\in\\{1,2,3\\}$, as previously
discussed. Hence $G$ is also planar.

(a) $p_{j}^{1}p_{j}^{2}\in M$

(b) $p_{j}^{3}p_{j}^{4}\in M$

(c) $p_{j}^{5}p_{j}^{6}\in M$

Figure 4: Configurations by removing a bipartizing matching clause gadget of
size three.

In order to prove that $F$ is satisfiable if and only if $G\in\mathcal{BM}$,
we discuss some considerations related to bipartizing matchings of the clause
and variable gadgets. By Lemma 11, we know that the graph obtained by removing
a border from an odd $k$-pool admits a unique bipartizing matching for each
edge of the internal cycle, except that whose endvertices are adjacent to the
removed border. Furthermore, Lemma 10 implies that each external edge incident
to the neck of an induced head cannot be in any bipartizing matching of $G$.
Figure 4 shows the possible bipartizing matchings $M$, stressed edges, for the
clause gadget $G_{C_{j}}$ of clauses of size three. The black and white vertex
assignment represents the bipartition of $G_{C_{j}}-M$. Exactly one pair of
vertices $\ell_{j}(k,w)$ and $\ell_{j}(k,b)$ ($k\in\\{1,2,3\\}$) is such that
they have the same color, while the others pairs have opposite colors.
Precisely, we can see that $\ell_{j}(k,w)$ has the same color for each pair
with opposite color vertices as well as $\ell_{j}(k,b)$, for each bipartizing
matching of $G_{C_{j}}$. Hence, we can associate one literal $x_{j}^{1}$,
$x_{j}^{2}$, and $x_{j}^{3}$ to each pair of vertices $\ell_{j}(k,w)$ and
$\ell_{j}(k,b)$, $k\in\\{1,2,3\\}$. A similar analysis can be done for clause
gadgets of clauses of size two.

In the same way, each variable gadget $G_{X_{i}}$ admits two possible
bipartizing matchings $M$, as depicted in Figure 5. We can see that the pair
$d_{i}(3,b)$ and $d_{i}(3,w)$ has a different assignment for the other two
pairs $d_{i}(k,b)$ and $d_{i}(k,w)$, $k\in\\{1,2\\}$. Moreover, the last two
pairs have the same assignment, as depicted in Figure 5(a) and Figure 5(b).
One more detail is that the unique possibilities for such pairs is that
$d_{i}(3,b)$ and $d_{i}(3,w)$ have opposite assignments if and only if the
vertices $d_{i}(k,b)$ and $d_{i}(k,w)$ have the same assignment,
$k\in\\{1,2\\}$. Therefore we can associate the positive literal $x_{i}$ to
the pairs $d_{i}(k,b)$ and $d_{i}(k,w)$, $k\in\\{1,2\\}$, while
$\overline{x_{i}}$ can be represented by $d_{i}(3,b)$ and $d_{i}(3,w)$.

As observed above for clause gadgets, we can associate true value to the pair
of vertices $\ell_{j}(k,w)$ and $\ell_{j}(k,b)$ with same color,
$k\in\\{1,2,3\\}$. Hence exactly one of them is true, that is, exactly one
literal of $C_{j}$ is true. Moreover, each variable gadget has two positive
literals and one negative. Hence, if $G\in\mathcal{BM}$, then every clause
gadget has exactly one true literal and every variable has a correct truth
assignment, which implies that $F$ is satisfiable.

Conversely, if $F$ is satisfiable, then each clause has exactly one true
literal. Thus, for each clause gadget $G_{C_{j}}$ we associate a same color to
the pair of vertices corresponding to its true literal. By Figure 4, there is
an appropriate choice of a bipartizing matching for each true literal of
$C_{j}$. The same holds for each variable gadget. ∎

(a) $p_{i}^{1}p_{i}^{2}\in M$.

(b) $p_{i}^{5}p_{i}^{6}\in M$.

Figure 5: All configurations by removing a bipartizing matching $M$ of a
variable gadget.

Proof of Theorem 1. Let $G$ be the graph obtained by the construction in
Theorem 12. Since the only vertices of degree 5 are those $p^{4}_{i}$ in the
variable gadgets, we slightly modify the variable gadget as in Figure 6(a). In
Figure 2 we can see that vertex $h_{6}$ has degree $3$, which allows us to use
it to connect the variable gadget to the clause one. Figure 6(b) and Figure
6(c) show the possible bipartizing matchings of the new variable gadget. Since
such configurations are analogous to those of the original variable gadget,
with respect to the vertex that connect to clause gadgets, the theorem
follows.

(a) Modified variable gadget.

(b) $p_{i}^{1}p_{i}^{2}\in M$.

(c) $p_{i}^{5}p_{i}^{6}\in M$.

Figure 6: The modified variable gadget and its all configurations given by
removing a bipartizing matching $M$.

##  4 Positive Results

###  4.1 Graphs having Bounded Dominating Sets.

A dominating set $S\subseteq V(G)$ of a graph $G=(V,E)$ is a vertex set such
that all vertices of $V(G)\setminus S$ has a neighbor in $S$. The cardinality
of a minimum dominating set of $G$ is the domination number of $G$. Now,
consider that the domination number of the input graph $G$ is bounded by a
constant $k$.

###### Theorem 5(a).

A dominating set of order at most $k$ can be found in time $O(n^{k+2})$, by
enumerating each vertex subset of size $k$ and checking in time $O(n(G)+m(G))$
whether it is a dominating set or not. Let $D$ be such a dominating set of $G$
of order at most $k$. Let $\mathcal{P_{D}}$ be the set of all bipartitions
$P_{D}$ of $D$ into sets $A_{D}$ and $B_{D}$, such that $G[A_{D}]$ and
$G[B_{D}]$ do not have any vertex of degree 2. Note that
$|\mathcal{P_{D}}|=O(2^{k})$.

Let $P_{D}\in\mathcal{P_{D}}$ be a bipartition of $D$. We partition all the
other vertices of $V(G)\setminus V(D)$ in such a way that $P_{D}$ defines a
bipartition of $G-M_{D}$, if one exists, where $M_{D}$ is a matching that will
be removed, given the choice of $D$. We do the following tests and operations
for each vertex $v\in V(G)\setminus V(D)$:

  * •

If $d_{G[A_{D}\cup\\{v\\}]}(v)\geq 2$ and $d_{G[B_{D}]}(v)\geq 2$, then
$P_{D}$ is not a valid partition;

  * •

If $d_{G[A_{D}\cup\\{v\\}]}(v)\geq 2$, then $B_{D}\leftarrow
B_{D}\cup\\{v\\}$;

  * •

If $d_{G[B_{D}\cup\\{v\\}]}(v)\geq 2$, then $A_{D}\leftarrow
A_{D}\cup\\{v\\}$.

Iteratively we allocate the vertices of $V(G)\setminus V(D)$ as described
above into the respective sets $A_{D}$ e $B_{D}$, or we stop if it is not
possible to acquire a valid bipartition. After these operations, set
$V^{\prime}=V(G)\setminus\\{A_{D}\cup B_{D}\\}$ can be partitioned into three
sets:

  * •

$X=\\{u\in V^{\prime}:d_{G[A_{D}\cup\\{u\\}]}(u)=1\mbox{ and
}d_{G[B_{D}\cup\\{u\\}]}(u)=0\\}$;

  * •

$Y=\\{u\in V^{\prime}:d_{G[A_{D}\cup\\{u\\}]}(u)=0\mbox{ and
}d_{G[B_{D}\cup\\{u\\}]}(u)=1\\}$;

  * •

$Z=\\{u\in V^{\prime}:d_{G[A_{D}\cup\\{u\\}]}(u)=1\mbox{ and
}d_{G[B_{D}\cup\\{u\\}]}(u)=1\\}$;

Since every vertex in $V(G)\setminus V(D)$ has a neighbor in $D$, it follows
that the neighborhood of all the vertices of $V^{\prime\prime}=X\cup Y\cup Z$
in $A_{D}\cup B_{D}$ is in $D$. In this way, we can make a choice of a
matching $M_{D}$ to be removed, where the vertices of $V^{\prime\prime}$ are
allocated either in $A_{D}$ or in $B_{D}$, and $G-M_{D}$ is bipartite. Since
each vertex of $D$ can be matched to at most one vertex of $V^{\prime\prime}$,
there are $O\left((n-k)^{k}\right)$ possibilities of choices for $M_{D}$.

Hence we obtain the following complexity:

$O\left(\sum_{i=1}^{k}n^{i+2}\cdot 2^{i}\cdot(n-i)^{i}\right)=O\left(k\cdot
2^{k}\cdot n^{k+2}\cdot(n-k)^{k}\right)=O\left(n^{2k+2}\right).\qed$

Theorem 5(a) allows us to prove Theorem 5(b).

###### Theorem 5(b).

Every connected $P_{5}$-free graph has a dominating clique or a dominating
$P_{3}$ [15], and graphs in $\mathcal{BM}$ do not admit $K_{5}$ as a subgraph.
Thus, $P_{5}$-free graphs in $\mathcal{BM}$ have domination number at most
four. ∎

###  4.2 Graphs with Only Triangles as Odd Cycles.

Consider now a slightly general version of BM , where some edges are forbidden
to be in any bipartizing matching.

Allowed Bipartizing Matching (ABM)
Instance: A graph $G$ and a set $F$ of edges of $G$.
Task: Decide whether $G$ has a bipartizing matching $M$ that does not
intersect $F$, and determine such a matching if it exists.

A matching $M$ as in ABM is called an allowed bipartizing matching of $(G,F)$.

We may clearly assume $G$ as connected and bridge-free. Moreover, note that if
$(G,F)$ has an allowed bipartizing matching, then $G\in{\sc BM}$.

###### Theorem 5(c).

Let $G$ be a graph having no $C_{2k+1}$, for $k>1$, and let $F\subseteq E(G)$.

First, consider $G$ a non-bipartite graph with no cut vertex, and let
$v_{1}v_{2}v_{3}v_{1}$ be an triangle of $G$. Without loss of generality, we
can assume that there is a vertex, say $v_{1}$, such that
$\\{v_{1}v_{2},v_{1}v_{3}\\}$ is not an edge cut, otherwise $G$ would be a
triangle. Then $G-\\{v_{1}v_{2},v_{1}v_{3}\\}$ has a path $P$ from $v_{1}$ to
$\\{v_{2},v_{3}\\}$. Consider $P$ as a longest one of length at least $2$, and
let $v_{2}$ be the first vertex reached by $P$ between $v_{2}$ and $v_{3}$.
Thus $P$ must be of the form $v_{1}uv_{2}$, otherwise either
$G[V(P)\cup\\{v_{3}\\}]$ or $G[V(P)]$ contains an odd cycle of length at least
$5$, when $P$ has either an even or odd number of vertices, respectively.

If $w\in V(G)$ has exactly one neighbor $z\in\\{v_{1},v_{2},v_{3},u\\}$, then
$w$ is in a path $P^{\prime}$ of length at least two between $z$ and
$z^{\prime}\in\\{v_{1},v_{2},v_{3},u\\}$, $z\neq z^{\prime}$. Hence
$P^{\prime}\cup\\{v_{1},v_{2},v_{3},u\\}$ contains an odd cycle of length at
least 5. Hence consider that $w$ has at least two neighbors in
$\\{v_{1},v_{2},v_{3},u\\}$. If $uv_{3}\in E(G)$, then
$G[\\{v_{1},v_{2},v_{3},u\\}]$ is a $K_{4}$, which implies that
$V(G)=\\{v_{1},v_{2},v_{3},u\\}$, since $\\{w,v_{1},v_{2},v_{3},u\\}$ induces
an odd cycle. Thus $G$ has an allowed bipartizing matching if and only if a
maximal matching of $G$ no intersecting $F$. Otherwise if $uv_{3}\notin E(G)$,
then $w$ must be adjacent to either $u$ and $v_{3}$ or to $v_{1}$ and $v_{2}$,
and no other vertex in $\\{v_{1},v_{2},v_{3},u\\}$. Moreover, the vertices
adjacent to both $u$ and $v_{3}$ induce an independent set of $G$, as well as
the vertices adjacent to both $v_{1}$ and $v_{2}$. In this case we can see
that $G$ has an allowed bipartizing matching if and only if $v_{1}v_{2}\notin
F$.

Now, we consider a block decomposition of $G$ with block-cut tree $T$. Let $B$
be a block containing exactly one cut-vertex $v$, that is, $B$ is a leaf in
$T$. If $(B,F)$ has an allowed bipartizing matching which is not incident to
$v$, then $(G,F)$ has an allowed bipartizing matching if and only if
$(G^{{}^{\prime}},F)$ also admits one, where
$G^{{}^{\prime}}=\left(\left(V(G)\setminus
V(B)\right)\cup\\{v\\},E(G)\setminus E(B)\right)$. Otherwise, $(G,F)$ has an
allowed bipartizing matching if and only if $(B,F)$ and
$(G^{{}^{\prime\prime}},F^{{}^{\prime\prime}})$ admit allowed bipartizing
matchings, where $G^{{}^{\prime\prime}}=\left(\left(V(G)\setminus
V(B)\right)\cup\\{v\\},E(G)\setminus E(B)\right)$ and
$F^{{}^{\prime\prime}}=F\cup\\{uv~{}|~{}u\in N_{G^{{}^{\prime\prime}}}(v)\\}$.

As in a block the desired matchings can be found, if any exists, in polynomial
time, it is easy to see that we can solve ABM in polynomial time. ∎

##  5 Fixed-Parameter Tractability

In this section, we consider the parameterized complexity of BM , and present
an analysis of its complexity when parameterized by some classical parameters.

######  Definition 1.

The clique-width of a graph $G$, denoted by $cwd(G)$, is defined as the
minimum number of labels needed to construct $G$, using the following four
operations [11]:

  1. 1.

Create a single vertex $v$ with an integer label $\ell$ (denoted by
$\ell(v)$);

  2. 2.

Disjoint union of two graphs (i.e. co-join) (denoted by $\oplus$);

  3. 3.

Join by an edge every vertex labeled $i$ to every vertex labeled $j$ for
$i\neq j$ (denoted by $\eta(i,j)$);

  4. 4.

Relabeling all vertices with label $i$ by label $j$ (denoted by $\rho(i,j)$).

Courcelle et al. [21] stated that for any graph $G$ with clique-width bounded
by a constant $k$, and for each graph property $\Pi$ that can be formulated in
a monadic second order logic ($MSOL_{1}$), there is an $O(f(cwd(G))\cdot n)$
algorithm that decides if $G$ satisfies $\Pi$ [18, 22, 19, 21, 20]. In
$MSOL_{1}$, the graph is described by a set of vertices $V$ and a binary
adjacency relation $edge(.,.)$, and the graph property in question may be
defined in terms of sets of vertices of the given graph, but not in terms of
sets of edges. Therefore, in order to show the fixed-parameter tractability of
BM when parameterized by clique-width, it remains to show that the related
property is $MSOL_{1}$-expressible.

###### Theorem 6.

Remind that the problem of determining whether $G$ admits an odd decycling
matching is equivalent to determine whether $G$ admits an $(2,1)$-coloring,
which is a $2$-coloring. Thus, it is enough to show that the property “$G$ has
an $(2,1)$-coloring” is $MSOL_{1}$-expressible.

We construct a formula $\varphi(G)$ such that $G\in{\sc
BM}\Leftrightarrow\varphi(G)$ as follows:

$\displaystyle\exists~{}S_{1},S_{2}\subseteq V(G)~{}:$
$\displaystyle~{}(S_{1}~{}\cap~{}S_{2}~{}=~{}\emptyset)~{}\wedge$
$\displaystyle~{}(S_{1}~{}\cup~{}S_{2}~{}=~{}V(G))~{}\wedge$
$\displaystyle~{}(\forall~{}v_{1}\in~{}S_{1}[~{}\nexists~{}u_{1},w_{1}\in
S_{1}:~{}(u_{1}\neq
w_{1})\wedge~{}edge(u_{1},v_{1})\wedge~{}edge(w_{1},v_{1})])~{}\wedge$
$\displaystyle~{}(\forall~{}v_{2}\in~{}S_{2}[~{}\nexists~{}u_{2},w_{2}\in
S_{2}:~{}(u_{2}\neq
w_{2})\wedge~{}edge(u_{2},v_{2})\wedge~{}edge(w_{2},v_{2})]).\qed$

Since clique-width generalizes several graph parameters [38], we obtain the
following corollary.

######  Corollary 13.

Odd Decycling Matching is in FPT when parameterized by the following
parameters:

  * •

neighborhood diversity;

  * •

treewidth;

  * •

pathwidth;

  * •

feedback vertex set;

  * •

vertex cover.

Since $K_{5}$ is a forbidden subgraph, chordal graphs in $\mathcal{BM}$ have
bounded treewidth [44], and thus, BM is polynomial-time solvable for this
class and Corollary 7 follows.

Courcelle’s theorem is a good classification tool, however it does not provide
a precise FPT-running time. The next result shows the exact upper bound for BM
parameterized by the vertex cover number $vc(G)$ of $G$. A vertex cover
$S\subseteq V(G)$ of $G$ is a vertex subset such that $G[V(G)\setminus S]$ has
no edge, that is, it is an independent set. The vertex cover number is the
cardinality of a minimum vertex cover.

######  Theorem 14.

BM admits a $2^{O(vc(G))}\cdot n(G)$ algorithm.

###### Proof.

Let $S$ be a vertex cover of $G$ such that $|S|=vc(G)$. The algorithm follows
in a similar way to the algorithm in the proof of Theorem 5(a). Let
$\mathcal{P_{S}}$ be the set of all bipartitions $P_{S}$ of $S$ into sets
$A_{S}$ and $B_{S}$, such that $S[A_{S}]$ and $S[B_{S}]$ do not have any
vertex of degree 2. Note that $|\mathcal{P_{S}}|=O(2^{k})$.

For each $P_{S}\in\mathcal{P_{S}}$, we will check if an odd decycling matching
of $G$ can be obtained from $P_{S}$ by applying the following operations:

For each vertex $v\in V(G)\setminus V(S)$ do

  * •

If $d_{A_{S}}(v)\geq 2$ and $d_{B_{S}}(v)\geq 2$, then $P_{S}$ is not a valid
partial partition;

  * •

If $d_{A_{S}}(v)\geq 2$, then $A_{S}\leftarrow A_{S}\cup\\{v\\}$;

  * •

If $d_{B_{S}}(v)\geq 2$, then $B_{S}\leftarrow B_{S}\cup\\{v\\}$.

After that, if for all vertices the first condition is not true, then
$V(G)\setminus V(A_{S}\cup B_{S})$ can be partitioned into three sets:

  * •

$X=\\{u\in V(G)\setminus V(A_{S}\cup B_{S}):d_{A_{S}}(u)=1\mbox{ and
}d_{B_{S}}(u)=0\\}$;

  * •

$Y=\\{u\in V(G)\setminus V(A_{S}\cup B_{S}):d_{A_{S}}(u)=0\mbox{ and
}d_{B_{S}}(u)=1\\}$;

  * •

$Z=\\{u\in V(G)\setminus V(A_{S}\cup B_{S}):d_{A_{S}}(u)=1\mbox{ and
}d_{B_{S}}(u)=1\\}$;

Since $V(G)\setminus V(S)$ is an independent set, it follows that all edges of
vertices in $X\cup Y$ can remain in the graph $G$. For each $z\in Z$, denote
by $a_{z}\in A_{S}$ and $b_{z}\in B_{S}$ the neighbors of $z$ in $G$.

Now, we apply a bounded search tree algorithm. While $G[A_{S}]$ and $G[B_{S}]$
have both maximum degree equal to one, and $Z\neq\emptyset$ do. Remove a
vertex $z\in Z$ and apply recursively the algorithm for the following cases:

  1. 1.

$z$ is added to $A_{S}$, and all vertices in $Z\cap N(a_{z})$ is added to
$B_{S}$.

  2. 2.

$z$ is added to $B_{S}$, and all vertices in $Z\cap N(b_{z})$ is added to
$A_{S}$.

Note that the search tree $T$ has height equals $vc(G)+1$. Finally, if $T$ has
a leaf representing a configuration with $G[A_{S}]$ and $G[B_{S}]$ having both
maximum degree equal to one, and $Z=\emptyset$, then $G\in\mathcal{BM}$. ∎

Now we analyze the parameterized complexity of BM considering the neighborhood
diversity number, $nd(G)$, as parameter.

######  Definition 2.

A graph $G(V,E)$ has neighborhood diversity $nd(G)=t$ if we can partition $V$
into $t$ sets $V_{1},\dotsc,V_{t}$ such that, for every $v\in V$ and all
$i\in{1,\dotsc,t}$, either $v$ is adjacent to every vertex in $V_{i}$ or it is
adjacent to none of them. Note that each part $V_{i}$ of $G$ is either a
clique or an independent set.

The neighborhood diversity parameter is a natural generalization of the vertex
cover number. In 2012, Lampis [38] showed that for every graph $G$ we have
$nd(G)\leq 2^{vc(G)}+vc(G)$. The optimal neighborhood diversity decomposition
of a graph $G$ can be computed in $\mathcal{O}(n^{3})$ time [38].

######  Theorem 15.

BM admits a kernel with at most $2\cdot nd(G)$ vertices when parameterized by
neighborhood diversity number.

###### Proof.

Given an instance $(G,F)$ of ABM such that $G$ is a graph and $F\subseteq
E(G)$ a set of forbidden edges. The kernelization algorithm consists on
applying the following reduction rules:

  1. 1.

If $G$ contains a $K_{5}$, then $G$ has no allowed odd decycling matching;
otherwise

  2. 2.

If a part $V_{i}$ induces a $K_{3}$ and exist two vertices in $V(G)\setminus
V_{i}$ adjacent to $V_{i}$, then $G$ has no allowed bipartizing matching;
otherwise

  3. 3.

If a subgraph of $G$ induces either a $K_{3}$ or a $K_{4}$ and does not admit
an allowed bipartizing matching, then $G$ has no allowed bipartizing matching;
otherwise

  4. 4.

Remove all parts isomorphic to a $K_{4}$;

  5. 5.

Remove all isolated parts isomorphic to a $K_{3}$;

  6. 6.

If $V_{i}$ is a part that induces a $K_{3}$ and $v\in V(G)\setminus V_{i}$ is
adjacent to $V_{i}$ (note that $\\{v\\}$ is a part), then remove $V_{i}$ and
$F\leftarrow F\cup\\{uv:u\in N_{G}(v)\setminus V_{i}\\}$;

  7. 7.

If a part $V_{i}$ induces an independent set of size at least 3, then contract
it into a single vertex $v_{i}$ (without parallel edges) and forbids all of
its incident edges.

It is easy to see that all reduction rules can be applied in polynomial time,
and after applying them any remaining part has size at most two. As the
resulting graph $G^{\prime}$ has $nd(G^{\prime})\leq nd(G)$ then
$|V(G^{\prime})|\leq 2\cdot nd(G)$. Thus, it remains to prove that the
application of each reduction rule is correct. As $K_{5}$ and $K_{5}-e$ are
forbidden subgraphs, and any bipartizing matching of a $K_{4}$ is a perfect
matching, then rules $1,2,3,4,5$, and $6$ can be applied in this order.
Finally, the correctness of rule $7$ follows from the following facts: $(i)$
if $G^{\prime}$ has an allowed bipartizing matching, then $G$ has also an
allowed bipartizing matching, because bipartite graph class is closed under
the operation of replacing vertices by a set of false twins, which have the
same neighborhood as the replaced vertex; $(ii)$ if $G^{\prime}$ does not
admit an allowed bipartizing matching then $G$ also does not admit an allowed
bipartizing matching, because if a contracted single vertex $v_{i}$ is in an
odd cycle in $G^{\prime}$, then even replacing $v_{i}$ by $V_{i}$
($|V_{i}|\geq 3$) and removing some incident edges of $V_{i}$ that form a
matching, some vertex of $V_{i}$ remains in an odd cycle. ∎

##  6 On $(2,d)$-Coloring Planar Graphs of Bounded Degree

Figure 7: The gadget used in the reduction of Theorem 3 $(2,2)$-colored with
colors black and white. The vertices $x$ and $y$ must receive different colors
in any $(2,2)$-coloring of $H$.

In this section we present the proofs of Theorems 3 and Corollary 4. The main
idea in the proof of Theorem 3 is to find a planar gadget $H$ (see Figure 7)
of maximum degree 6 containing two vertices $x$ and $y$ of degree at most 5
and such that they must receive different colors in any $(2,2)$-coloring of
$H$. We prove this on Lemma 16.

We complete the proof by a reduction from $(2,1)$-coloring for a planar graph
$G$ of maximum degree $4$, that is NP-complete by Theorem 1. Let $G^{\prime}$
be the graph obtained by adding for each vertex $v$ of $G$ a gadget $H_{v}$ as
in Figure 7, such that $v$ is adjacent to only $x$ and $y$ in $H_{v}$.
Therefore it follows that $G^{\prime}$ is a planar graph of maximum degree 6.

If $G\in\mathcal{BM}$, then each vertex $v$ of $G$ can be colored in such a
way that $v$ has at most one neighbor colored as itself and then $v$ can have
one more neighbor in $H_{v}$ with the same color. We can complete the
$(2,2)$-coloring of $G^{\prime}$ as that one depicted in Figure 7, where the
black and white vertices define the bipartition. Conversely, if $G^{\prime}$
admits a $(2,2)$-coloring $c$, then each vertex $v\in V(G)$ has exactly one
neighbor in $H_{v}$ colored as itself, which implies that $v$ admits at most
one more neighbor in $G$ colored as the same way. Hence $c$ restricted to the
vertices of $G$ is a $(2,1)$-coloring of $G$, and the theorem follows.

Next we present the proof of Lemma 16. In a first observation, for every pair
of vertices $u,v\in V(G)$ that share at least $2d+1$ neighbors, it follows
that both $u$ and $v$ must have the same color in any $(2,d)$-coloring of $G$.
Otherwise, one of them has at least $d+1$ neighbors with the same color as
itself. Therefore, by simplicity, we omit the complete neighborhood in Figure
7 of the vertices $w_{i}$, $w_{i}^{\prime}$, $y$, and $y_{3}$,
$i\in\\{1,2\\}$, where $w_{i}$ ($y$) shares $5$ neighbors with
$w_{i}^{\prime}$ ($y_{3}$). We can see that $w_{i}$, $w_{i}^{\prime}$,
$y_{1}$, $y_{3}$ and $x_{1}$ have degree $6$, while $x$ and $y$ have degree 5.

######  Lemma 16.

In any $(2,2)$-coloring of $H$, $x$ and $y$ must have distinct colors.

###### Proof.

As $w_{i}$ and $w_{i}^{\prime}$ shares $5$ neighbors, $i\in\\{1,2\\}$, it
follows that they must receive the same color in any $(2,2)$-coloring of $H$.
The same occurs for $y$ and $y_{3}$. In this way, $w_{i}$ and $w_{i}^{\prime}$
can be seen as the same vertex in terms of any $(2,2)$-coloring of $G$,
implying that $x$ and $y_{1}$ also “shares $5$ neighbors” with respect to the
coloring. This implies that $x$ and $y_{1}$ must receive the same color as
well. Now it is enough to see that at least one vertex in
$N_{H}(y_{1})\setminus\\{y,y_{3}\\}$ must receive the same color as $y_{1}$,
otherwise $x_{1}$ would have four vertices with the same color. Therefore, the
color of $y$ and $y_{3}$ have to be different from that of $y_{1}$, implying
that $x$ and $y$ receive different colors. ∎

We can use the same approach in the proof of Theorem 3 to obtain the bound of
$2d+2$ on the maximum degree on the NP-completeness of $(2,3)$-color planar
graphs. We just modify the gadget used in Theorem 3 as in Figure 8. With the
same arguments, we can see that $y_{1}$ must be adjacent to at least two
vertices of the same color in $N_{H}(y_{1})\setminus\\{y,y_{3}\\}$, otherwise
$x_{1}$ or $x_{2}$ would have four neighbors of the same color as themselves.
Since $x$ and $y$ have degree 7 and receive different colors in any
$(2,3)$-coloring of $H$, we can use the same strategy of adding a gadget $H$
of Figure 8 to each vertex of a planar graph $G$ of maximum degree 6,
obtaining a new graph $G^{\prime}$ of maximum degree 8. We conclude the
reduction from Theorem 3, that ensures the NP-completeness for $G$. In this
way, it follows that Corollary 4 follows.

Figure 8: The gadget used in the reduction of Corollary 4 $(2,3)$-colored with
colors black and white. The vertices $x$ and $y$ must receive different colors
in any $(2,3)$-coloring of $H$.

It is not hard to see that we can extend the idea to values of $d$ greater
than $3$. The central idea is in taking a vertex that has at least $d-1$
vertices of the same color as itself in any $(2,d)$-coloring. This holds for
$y_{1}$ in the both previous reduction. Then, we can add $d-1$ structures in
the neighborhood of $y_{3}$, like in Figure 8, in order to ensure that $y_{3}$
has $d-1$ one neighbors colored as itself in each structure. We can obtain
such neighbors by extending the neighborhood of each $x_{i}$ as in Figure 9(a)
and Figure 9(b), for $(2,4)$-coloring and $(2,5)$-coloring, respectively. We
can see that each vertex $x_{i}$ cannot receive the same color as all of its
neighbors less $x$. So $x$ has at least one neighbor colored as itself for
each $x_{i}$, $1\leq i\leq d-1$ implying that $x$ and $y$ must receive
different colors in any $(2,d)$-color of $H$. Hence we can use this gadget in
order to obtain a $(2,d)$-coloring of a planar graph $G$ by adding $H$ to each
vertex $v$ of $G$, as in the proofs of Theorem 3 and Corollary 4, where $v$ is
adjacent only to $x$ and $y$ in $H$, by using the gadget for $(2,d-1)$-color
$G$.

It is not hard to see that the above construction cannot be applied in
general, since the degree of $x$ increases in a quadratic way on $d$. Even so,
we can see that it gives an upper bound on the maximum degree better than
$4d+3$ for $d\leq 7$.

(a) Gadget for $(2,4)$-coloring.

(b) Gadget for $(2,5)$-coloring.

Figure 9: Generalized gadgets for $(2,d)$-color planar graphs.

##  7 Conclusion

In this paper we have obtained the complete dichotomy on the computational
complexity for $(2,1)$-color a planar graph in terms of the maximum degree,
where all graphs of maximum degree $3$ admits a bipartizing matching and we
prove the NP-completeness for maximum degree $4$. We extended the result for
$(2,2)$-coloring and $(2,3)$-coloring. We left open Question 2 restricted
$(2,d)$color planar graphs. We also give some parameterized complexity
results, proving that bipartizing a graph by the removal of a matching is FPT
when parameterized by the clique-width, which results in polynomial-time
algorithms for a number of important graph classes.

Interesting properties regarding the chromatic number of graphs in
$\mathcal{BM}$ can be proposed. For example, which graphs $G\in\mathcal{BM}$
are such that $\chi(G-M)\leq\chi(G)$, for a bipartizing matching $M$ of $G$?
Moreover, what is the maximum size of the gap between $\chi(G-M)$ and
$\chi(G)$?

## References

  * [1] Abdullah, A. On graph bipartization.  In ISCAS ’92 (1992), vol. 4, pp. 1847–1850.
  * [2] Agrawal, A., Jain, P., Kanesh, L., Misra, P., and Saurabh, S. Exploring the Kernelization Borders for Hitting Cycles.  In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018) (Dagstuhl, Germany, 2019), vol. 115 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, pp. 14:1–14:14.
  * [3] Alon, N., and Stav, U. Hardness of edge-modification problems.  Theory Comput. Sci. 410, 47-49 (2009), 4920–4927.
  * [4] Andrews, J., and Jacobson, M. On a generalization of chromatic number.  In Proc. Sixteenth Southeastern International Conference on Combinatorics, Graph Theory and Computing (1985), vol. 47, pp. 18–33.
  * [5] Angelini, P., Bekos, M. A., De Luca, F., Didimo, W., Kaufmann, M., Kobourov, S., Montecchiani, F., Raftopoulou, C. N., Roselli, V., and Symvonis, A. Vertex-coloring with defects.  J. Graph Algor. Appl. 21, 3 (2017), 313–340.
  * [6] Axenovich, M., Ueckerdt, T., and Weiner, P. Splitting planar graphs of girth 6 into two linear forests with short paths.  J. Graph Theory 85, 3 (2017), 601–618.
  * [7] Bang-Jensen, J., and Bessy, S. Degree-constrained 2-partitions of graphs.  Theo. Comp. Sci. (2019).  in press.
  * [8] Bodlaender, H. L. A partial $k$-arboretum of graphs with bounded treewidth.  Theo. Comp. Sci. 209, 1–2 (1998), 1–45.
  * [9] Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M., and Paulusma, D. Independent feedback vertex set for P5-free graphs.  Algorithmica (2018).
  * [10] Borodin, O., Kostochka, A., and Yancey, M. On $1$-improper $2$-coloring of sparse graphs.  Discrete Math. 313, 22 (2013), 2638–2649.
  * [11] Brandstädt, A., Dragan, F. F., Le, H.-O., and Mosca, R. New graph classes of bounded clique-width.  Theo. Comput. Sys. 38, 5 (2005), 623–645.
  * [12] Brandstädt, A., Engelfriet, J., Le, H.-O., and Lozin, V. V. Clique-width for $4$-vertex forbidden subgraphs.  Theory Comput. Syst. 39, 4 (2006), 561–590.
  * [13] Brandstädt, A., Klembt, T., and Mahfud, S. $P_{6}$\- and triangle-free graphs revisited: structure and bounded clique-width.  Discrete Math. Theor. Comput. Sci. 8 (2006), 173–188.
  * [14] Burzyn, P., Bonomo, F., and Durán, G. NP-completeness results for edge modification problems.  Discrete Appl. Math. 154, 13 (2006), 1824–1844.
  * [15] Camby, E., and Schaudt, O. A new characterization of $P_{k}$-free graphs.  Algorithmica 75, 1 (2016), 205–217.
  * [16] Choi, H.-A., Nakajima, K., and Rim, C. S. Graph bipartization and via minimization.  SIAM J. Discrete Math. 2, 1 (1989), 38–47.
  * [17] Chuangpishit, H., Lafond, M., and Narayanan, L. Editing graphs to satisfy diversity requirements.  In Combinatorial Optimization and Applications (COCOA 2018) (Cham, 2018), Springer International Publishing, pp. 154–168.
  * [18] Courcelle, B. The monadic second-order logic of graphs. i. recognizable sets of finite graphs.  Inf. Comput. 85, 1 (1990), 12–75.
  * [19] Courcelle, B. Handbook of graph grammars and computing by graph transformation.  In The Expression of Graph Properties and Graph Transformations in Monadic Second-order Logic, G. Rozenberg, Ed. World Scientific Publishing Co., Inc., River Edge, NJ, USA, 1997, pp. 313–400.
  * [20] Courcelle, B., and Engelfriet, J. Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach.  Cambridge University Press, New York, NY, USA, 2012.
  * [21] Courcelle, B., Makowsky, J. A., and Rotics, U. Linear time solvable optimization problems on graphs of bounded clique-width.  Theory Comput. Sys. 33, 2 (2000), 125–150.
  * [22] Courcelle, B., and Mosbah, M. Monadic second-order evaluations on tree-decomposable graphs.  Theor. Comput. Sci. 109, 1-2 (1993), 49–82.
  * [23] Cowen, L., Cowen, R., and Woodall, D. Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency.  J. Graph Theory 10 (1986), 187–195.
  * [24] Cowen, L., Goddard, W., and Jesurum, C. E. Defective coloring revisited.  J. Graph Theory 24, 3 (1997), 205–219.
  * [25] Cygan, M., Fomin, F. V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. Parameterized Algorithms.  Springer, 2015.
  * [26] Diestel, R. Graph Theory, vol. 173.  Springer-Verlag, 4th edition, 2010.
  * [27] Dorbec, P., Montassier, M., and Ochem, P. Vertex partitions of graphs into cographs and stars.  J. Graph Theory 75, 1 (2014), 75–90.
  * [28] Downey, R. G., and Fellows, M. R. Fundamentals of Parameterized Complexity.  Texts in Computer Science. Springer, 2013.
  * [29] Eaton, N., and Hull, T. Defective list colorings of planar graphs.  Bull. Inst. Combin. Appl 25 (1999), 79–87.
  * [30] Furmańczyk, H., Kubale, M., and Radziszowski, S. On bipartization of cubic graphs by removal of an independent set.  Discrete Appl. Math. 209 (2016), 115–121.
  * [31] García-Vázquez, P. On the bipartite vertex frustration of graphs.  Electronic Notes in Discrete Mathematics 54 (2016), 289 – 294\.
  * [32] Garey, M., Johnson, D., and Stockmeyer, L. Some simplified NP-complete graph problems.  Theory Comput. Sci. 1, 3 (1976), 237–267.
  * [33] Gimbel, J., and Nešetřil, J. Partitions of graphs into cographs.  Discrete Math. 310, 24 (2010), 3437 – 3445.
  * [34] Golumbic, M. C., and Rotics, U. On the clique-width of some perfect graph classes.  Int. J. Found. Comput. Sci. 11, 03 (2000), 423–443.
  * [35] Guillemot, S., Havet, F., Paul, C., and Perez, A. On the (non-)existence of polynomial kernels for $p$-free edge modification problems.  Algorithmica 65, 4 (2012), 900–926.
  * [36] Harary, F., and Jones, K. Conditional colorability ii: Bipartite variations.  In Proc. Sundance Cont. Combinatorics and related topics, Congr. Numer. (1985), vol. 50, pp. 205–2018.
  * [37] Hopcroft, J., and Tarjan, R. Efficient planarity testing.  J. ACM 21, 4 (1974), 549–568.
  * [38] Lampis, M. Algorithmic meta-theorems for restrictions of treewidth.  Algorithmica 64, 1 (2012), 19–37.
  * [39] Lima, C. V., Rautenbach, D., Souza, U. S., and Szwarcfiter, J. L. Decycling with a matching.  Infor. Proc. Letters 124 (2017), 26 – 29.
  * [40] Lovász, L. On decomposition of graphs.  Studia Sci. Math. Hungar. 1 (1966), 237–238.
  * [41] Mulzer, W., and Rote, G. Minimum-weight triangulation is NP-hard.  J. ACM 55, 2 (2008), 1–29.
  * [42] Natanzon, A., Shamir, R., and Sharan, R. Complexity classification of some edge modification problems.  Discrete Appl. Math. 113, 1 (2001), 109–128.
  * [43] Protti, F., and Souza, U. S. Decycling a graph by the removal of a matching: new algorithmic and structural aspects in some classes of graphs.  Discrete Mathematics & Theoretical Computer Science vol. 20 no. 2 (2018).
  * [44] Robertson, N., and Seymour, P. Graph minors. ii. algorithmic aspects of tree-width.  J. Algorith. 7, 3 (1986), 309 – 322.
  * [45] Schaefer, T. J. The complexity of satisfiability problems.  In STOC ’78 (1978), pp. 216–226.
  * [46] Thorup, M. All structured programs have small tree width and good register allocation.  Inf. Comput. 142, 2 (1998), 159–181.
  * [47] Yannakakis, M. Node-and edge-deletion NP-complete problems.  In STOC ’78 (1978), pp. 253–264.
  * [48] Yannakakis, M. Edge-deletion problems.  SIAM J. Comput. 10, 2 (1981), 297–309.
  * [49] Yarahmadi, Z., and Ashrafi, A. R. A fast algorithm for computing bipartite edge frustration number of $(3,6)$-fullerenes.  J. Theor. Comput. Chem. 13, 02 (2014), 1450014–1450025.