# Parameterized and Exact Algorithms for Class Domination Coloring ***A
preliminary version of this paper appeared in the proceedings of $43^{rd}$
International Conference on Current Trends in Theory and Practice of Computer
Science (SOFSEM 2016).

R. Krithika<EMAIL_ADDRESS>Indian Institute of Technology Palakkad,
Palakkad, India  Ashutosh Rai<EMAIL_ADDRESS>Indian Institute
of Technology Delhi, Delhi, India  Saket Saurabh†††The research leading to
these results has received funding from the European Research Council under
the European Union’s Seventh Framework Programme (FP7/2007-2013) / ERC grant
agreement no. 306992<EMAIL_ADDRESS>The Institute of Mathematical Sciences,
HBNI, Chennai, India and University of Bergen, Bergen, Norway  Prafullkumar
Tale‡‡‡This research is a part of a project that has received funding from the
European Research Council (ERC) under the European Union’s Horizon $2020$
research and innovation programme under grant agreement SYSTEMATICGRAPH (No.
$725978$<EMAIL_ADDRESS>CISPA Helmholtz Center for
Information Security, Saarbr$\ddot{\text{u}}$cken, Germany

###### Abstract

A class domination coloring (also called cd-Coloring or dominated coloring) of
a graph is a proper coloring in which every color class is contained in the
neighbourhood of some vertex. The minimum number of colors required for any
cd-coloring of $G$, denoted by $\chi_{cd}(G)$, is called the class domination
chromatic number (cd-chromatic number) of $G$. In this work, we consider two
problems associated with the cd-coloring of a graph in the context of exact
exponential-time algorithms and parameterized complexity. (1) Given a graph
$G$ on $n$ vertices, find its cd-chromatic number. (2) Given a graph $G$ and
integers $k$ and $q$, can we delete at most $k$ vertices such that the cd-
chromatic number of the resulting graph is at most $q$? For the first problem,
we give an exact algorithm with running time $\mathcal{O}(2^{n}n^{4}\log n)$.
Also, we show that the problem is with respect to the number $q$ of colors as
the parameter on chordal graphs. On graphs of girth at least 5, we show that
the problem also admits a kernel with $\mathcal{O}(q^{3})$ vertices. For the
second (deletion) problem, we show -hardness for each $q\geq 2$. Further, on
split graphs, we show that the problem is -hard if $q$ is a part of the input
and with respect to $k$ and $q$ as combined parameters. As recognizing graphs
with cd-chromatic number at most $q$ is -hard in general for $q\geq 4$, the
deletion problem is unlikely to be when parameterized by the size of the
deletion set on general graphs. We show fixed parameter tractability for
$q\in\\{2,3\\}$ using the known algorithms for finding a vertex cover and an
odd cycle transversal as subroutines.

††journal: Nuclear Physics B

##  1 Introduction

Graph coloring is a classical problem in the fields of combinatorics and
algorithm design. A proper coloring of a graph is an assignment of colors to
its vertices such that no two adjacent vertices receive the same color.
Equivalently, a proper coloring is a partition of the vertex set into
independent sets. In this context, these independent sets are also called
color classes. A proper coloring of a graph $G$ using $q$ colors is called a
$q$-coloring of $G$ and the minimum number of colors required in a proper
coloring is called as the chromatic number of $G$. Determining the chromatic
number of a graph is a classical -hard problem. This problem has been widely
investigated in the areas of exact algorithms [1, 2, 3, 4, 5, 6],
approximation algorithms [7, 8, 9, 10], and parameterized algorithms [11, 12,
13, 14]. Further, variants of the graph coloring like Edge-Chromatic Number,
Achromatic Number, $b$-Chromatic Number, Total Chromatic Number, Dominator
Coloring and Class Domination Coloring have also been well studied [15, 16,
17].

In this work, we initiate the study of Class Domination Coloring (also called
cd-Coloring or Dominated Coloring) in the realm of parameterized complexity
and exact exponential time algorithms. A cd-coloring is a proper coloring of
the graph in which every color class is contained in the neighbourhood of some
vertex. See Figure 1 for an example. The minimum number of colors needed in
any cd-coloring of $G$ is called the class domination chromatic number or cd-
chromatic number of $G$ and is denoted by $\chi_{cd}(G)$. Also, $G$ is said to
be $q$-cd-colorable if $\chi_{cd}(G)\leq q$. The cd-Coloring problem is
formally defined as follows.

cd-Coloring Input: A graph $G$ and a positive integer $q$. Question: Is
$\chi_{cd}(G)\leq q$?

cd-Coloring is -complete for $q\geq 4$ and polynomial-time solvable for $q\leq
3$ [18]. A characterization of graphs that admit 3-cd-colorings is also known
[18]. cd-Coloring has also been studied on many restricted graph classes like
split graphs, $P_{4}$-free graphs [18] and middle and central graphs of
$K_{1,n}$, $C_{n}$ and $P_{n}$ [19]. See also [20, 21, 22, 23, 24].

We study this problem in the context of exact exponential-time algorithms and
parameterized complexity. The field of exact algorithms typically deals with
designing algorithms for -hard problems that are faster than brute-force
search while the goal in parameterized complexity is to provide efficient
algorithms for -complete problems by switching from the classical view of
single-variate measure of the running time to a multi-variate one. In
parameterized complexity, we consider instances $(I,k)$ of a parameterized
problem $\Pi\subseteq\Sigma^{*}\times\mathbb{N}$, where $\Sigma$ is a finite
alphabet. Algorithms in this area have running times of the form
$f(k)|I|^{\mathcal{O}(1)}$, where $k$ is an integer measuring some part of the
instance. This integer $k$ is called the parameter, and a problem that admits
such an algorithm is said to be fixed-parameter tractable (). In most of the
cases, the solution size is taken to be the parameter, which means that this
approach results in efficient (polynomial-time) algorithms when the solution
is of small size. A _kernelization_ algorithm for a parameterized problem
$\Pi$ is a polynomial time procedure which takes as input an instance $(x,k)$
of $\Pi$ and returns an instance $(x^{\prime},k^{\prime})$ such that
$(x,k)\in\Pi$ if and only if $(x^{\prime},k^{\prime})\in\Pi$ and
$|x^{\prime}|\leq h(k)$ and $k^{\prime}\leq g(k)$, for some computable
functions $h,g$. The returned instance is called a kernel and $h(k)+g(k)$ is
its size. We say that $\Pi$ admits a polynomial kernel if $h$ and $g$ are
polynomials. For more background on parameterized complexity, we refer the
reader to the monographs [25, 26, 27, 28].

Figure 1: An example of a cd-Coloring of a graph

We first observe that parameterizing cd-Coloring by the solution size (which
is the number of colors) does not help in designing efficient algorithms as
the problem is para--hard (-hard even when the parameter is a constant).
Hence, this problem is unlikely to be when parameterized by the solution size.
Then, we describe an $\mathcal{O}(2^{n}n^{4}\log n)$-time algorithm for
finding the cd-chromatic number of a graph using polynomial method. Next, we
show that cd-Coloring is when parameterized by the number of colors and the
treewidth of the input graph. Further, we show that the problem is when
parameterized by the number of colors on chordal graphs. Kaminski and Lozin
[29] showed that determining if a graph of girth at least $g$ admits a proper
coloring with at most $q$ colors or not is -complete for any fixed $q\geq 3$
and $g\geq 3$. In particular, Chromatic Number is para--hard for graphs of
girth at least 5. In contrast, we show that cd-Coloring is on this graph class
and admits a kernel with $\mathcal{O}(q^{3})$ vertices.

On a graph $G$ that is not $q$-cd-colorable, a natural optimization question
is to check if we can delete at most $k$ vertices from $G$ such that the cd-
chromatic number of the resultant graph is at most $q$. We define this problem
as follows.

cd-Partization Input: Graph $G$, integers $k$ and $q$ Question: Does there
exist $S\subseteq V(G)$, $|S|\leq k$, such that $\chi_{cd}(G-S)\leq q$?

If $q$ is fixed, then we refer to the problem as $q$-cd-Partization. Once
again, from parameterized complexity point of view, this question is not
interesting on general graphs for values of $q$ greater than three, as in
those cases, an algorithm with deletion set (solution) size as the parameter
is a polynomial-time recognition algorithm for $q$-cd-colorable graphs. Hence,
the deletion question is interesting only on graphs where the recognition
problem is polynomial-time solvable. We show that $q$-cd-Partization is
-complete for each $q\geq 2$, and that for $q\in\\{2,3\\}$, the problem is
with respect to the solution size as the parameter. Our algorithms use the
known parameterized algorithms for finding a vertex cover and an odd cycle
transversal of a graph as subroutines. We also show that cd-Partization
remains -complete on split graphs and is when parameterized by the number of
colors and solution size.

##  2 Preliminaries

The set of integers $\\{1,2,\ldots,k\\}$ is denoted by $[k]$. All graphs
considered in this paper are finite, undirected and simple. For the terms
which are not explicitly defined here, we use standard notations from [30].
For a graph $G$, its vertex set is denoted by $V(G)$ and its edge set is
denoted by $E(G)$. For a vertex $v\in V(G)$, its (open) neighbourhood
$N_{G}(v)$ is the set of all vertices adjacent to it and its closed
neighborhood is the set $N_{G}(v)\cup\\{v\\}$. We omit the subscript in the
notation for neighbourhood if the graph under consideration is clear from the
context. The degree of a vertex $v$ is the size of its open neighborhood.

For a set $S\subseteq V(G)$, the subgraph of $G$ induced by $S$, denoted by
$G[S]$, is defined as the subgraph of $G$ with vertex set $S$ and edge set
$\\{(u,v)\in E(G):u,v\in S\\}$. The subgraph of $G$ obtained after deleting
$S$ (and the edges incident on it) is denoted as $G-S$. The girth of a graph
is the length of a smallest cycle. A set $D\subseteq V(G)$ is said to be a
dominating set of $G$ if every vertex in $V(G)\setminus D$ is adjacent to some
vertex in $D$.

A proper coloring of $G$ with $q$ colors is a function $f:V(G)\rightarrow[q]$
such that for all $(u,v)\in E(G)$, $f(u)\neq f(v)$. For a proper coloring $f$
of $G$ with $q$ colors and $i\in[q]$, $f^{-1}(i)\subseteq V(G)$ is called a
color class in the coloring $f$. The chromatic number $\chi(G)$ of $G$ is the
minimum number of colors required in a proper coloring of $G$. A clique is a
graph which has an edge between every pair of vertices. The clique number
$\omega(G)$ of $G$ is the size of a largest clique which is a subgraph of $G$.
A vertex cover is a set of vertices that contains at least one endpoint of
every edge in the graph. An independent set is a set of pairwise nonadjacent
vertices. A graph is said to be a bipartite graph if its vertex set can be
partitioned into two independent sets. An odd cycle transversal is a set of
vertices whose deletion from the graph results in a bipartite graph. A tree-
decomposition of a graph $G$ is a pair
$(\mathbb{T},\mathcal{X}=\\{X_{t}\\}_{t\in V({\mathbb{T}})})$ such that

  * 1.

$\bigcup_{t\in V(\mathbb{T})}{X_{t}}=V(G)$,

  * 2.

for every edge $(x,y)\in E(G)$ there is a $t\in V(\mathbb{T})$ such that
$\\{x,y\\}\subseteq X_{t}$, and

  * 3.

for every vertex $v\in V(G)$ the subgraph of $\mathbb{T}$ induced by the set
$\\{t\mid v\in X_{t}\\}$ is connected.

The width of a tree decomposition is $\max_{t\in V(\mathbb{T})}|X_{t}|-1$ and
the treewidth of $G$, denoted by ${\mathbf{tw}}(G)$, is the minimum width over
all tree decompositions of $G$. The syntax of Monadic Second Order Logic (MSO)
of graphs includes the logical connectives $\vee$, $\wedge$, $\neg$,
$\Rightarrow$, $\Leftrightarrow$, variables for vertices, edges, sets of
vertices, sets of edges, the quantifiers $\forall$, $\exists$ that can be
applied to these variables and the following five binary relations.

  * 1.

$u\in U$ where $u$ is a vertex variable and $U$ is a vertex set variable;

  * 2.

$e\in F$ where $e$ is an edge variable and $F$ is an edge set variable;

  * 3.

${\mathbf{inc}}(e,u)$, where $e$ is an edge variable, $u$ is a vertex
variable, and the interpretation is that the edge $e$ is incident with the
vertex $u$;

  * 4.

${\mathbf{adj}}(u,v)$, where $u$ and $v$ are vertex variables and the
interpretation is that $u$ and $v$ are adjacent;

  * 5.

equality of variables representing vertices, edges, sets of vertices, and sets
of edges.

For an MSO formula $\phi$, $||\phi||$ denotes the length of its encoding as a
string.

######  Theorem 1 (Courcelle’s theorem, [31, 32]).

Let $\phi$ be a graph property that is expressible in MSO. Suppose $G$ is a
graph on $n$ vertices with treewidth $tw$ equipped with the evaluation of all
the free variables of $\phi$. Then, there is an algorithm that verifies
whether $\phi$ is satisfied in $G$ in $f(||\phi||,tw)\cdot n$ time for some
computable function $f$.

We end the preliminaries section with following simple observations.

######  Observation 1.

If $G_{1},\ldots,G_{l}$ are the connected components of $G$, then
$\chi_{cd}(G)=\sum_{i=1}^{l}\chi_{cd}(G_{i})$.

######  Observation 2.

If $G$ is $q$-cd-colorable, then $G$ has a dominating set of size at most $q$.

##  3 Exact Algorithm for cd-Chromatic Number

Let $G$ denote the input graph on $n$ vertices. Given a coloring of $V(G)$, we
can check in polynomial time whether it is a cd-coloring or not. Therefore, to
compute $\chi_{cd}(G)$, we can iterate over all possible colorings of $V(G)$
with at most $n$ colors and return a valid cd-coloring that uses the minimum
number of colors. This brute force algorithm runs in $2^{\mathcal{O}(n\log
n)}$ time. In this section we present an algorithm which runs in
$\mathcal{O}(2^{n}n^{4}\log n)$ time. The idea for this algorithm is inspired
by an exact algorithm for $b$-Chromatic Number presented in [33]. We first
list some preliminaries on polynomials and Fast Fourier Transform following
the framework of [33].

A binary vector $\phi$ is a finite sequence of bits and $val(\phi)$ denotes
the integer $d$ of which $\phi$ is the binary representation. All vectors
considered here are binary vectors and are synonymous to binary numbers.
Further, they are the binary representations of integers less than $2^{n}$ and
are assumed to consist of $n$ bits. $\phi_{1}+\phi_{2}$ denotes the vector
obtained by the bitwise addition of the binary numbers (vectors) $\phi_{1}$
and $\phi_{2}$. Let $U=\\{u_{1},u_{2},\dots,u_{n}\\}$ denote a universe with a
fixed ordering on its elements. The characteristic vector of a set $S\subseteq
U$, denoted by $\psi(S)$, is the vector of length $|U|$ whose $j^{\text{th}}$
bit is $1$ if $u_{j}\in S$ and $0$ otherwise. The Hamming weight of a vector
$\phi$ is the number of $1$s in $\phi$ and it is denoted by
$\mathcal{H}(\phi)$. Observe that $\mathcal{H}(\psi(S))=|S|$. The Hamming
weight of an integer is define as hamming weight of its binary representation.
To obtain the claimed running time bound for our exponential-time algorithm,
we make use of the algorithm for multiplying polynomials based on the Fast
Fourier Transform.

######  Lemma 1 ([34]).

Two polynomials of degree at most $d$ over any commutative ring $\mathcal{R}$
can be multiplied using $\mathcal{O}(d\cdot\log d\cdot\log\log d)$ additions
and multiplications in $\mathcal{R}$.

Let $z$ denote an indeterminate variable. We use the monomial
$z^{val(\psi(S))}$ to represent the set $S\subseteq U$ and as a natural
extension, we use univariate polynomials to represent a family of sets.

######  Definition 1 (Characteristic Polynomial of a Family of Sets).

For a family $\mathcal{F}=\\{S_{1},S_{2},\dots,S_{q}\\}$ of subsets of $U$,
the characteristic polynomial of $\mathcal{F}$ is defined as
$p_{\psi}(\mathcal{F})=\sum_{i=1}^{q}z^{val(\psi(S_{i}))}$.

######  Definition 2 (Representative Polynomial).

For a polynomial $p(z)=\sum_{i=1}^{q}a_{i}\cdot z^{i}$, we define its
representative polynomial as $\sum_{i=1}^{q}b_{i}\cdot z^{i}$ where $b_{i}=1$
if $a_{i}\neq 0$ and $b_{i}=0$ if $a_{i}=0$.

######  Definition 3 (Hamming Projection).

The Hamming projection of the polynomial $p(z)=\sum_{i=1}^{q}a_{i}\cdot z^{i}$
to the integer $h$ is defined as
$\mathcal{H}_{h}(p(z)):=\sum_{i=1}^{q}b_{i}\cdot z^{i}$ where $b_{i}=a_{i}$ if
$\mathcal{H}(i)=h$ and $b_{i}=0$ otherwise.

Next, for two sets $S_{1},S_{2}\subseteq U$, we define a modified
multiplication operation $(\star)$ of the monomials $z^{\psi(S_{1})}$ and
$z^{\psi(S_{2})}$ in the following way.

$z^{val(\psi(S_{1}))}\star
z^{val(\psi(S_{2}))}=\begin{cases}z^{val(\psi(S_{1}))+val(\psi(S_{2}))}&\text{if
}S_{1}\cap S_{2}=\emptyset\\\ 0&\text{otherwise}\end{cases}$

For a polynomial function $p(z)$ of $z$ and a positive integer $\ell\geq 2$,
we inductively define the polynomial $p(z)^{\ell}$ as
$p(z)^{\ell}:=p(z)^{\ell-1}\star p(z)$. Here, coefficients of monomials follow
addition and multiplications defined over underlying field. We now describe an
algorithm for implementing the $\star$ operation using the standard
multiplication operation and the notion of Hamming weights of bit strings
associated with exponents.

Input: Two polynomials $q(z),r(z)$ of degree at most $2^{n}$

Output: $q(z)\star r(z)$

1 Initialize polynomials $t(z)$ and $t^{\prime}(z)$ to 0

2

3for  _each ordered pair $(i,j)\text{ such that }i+j\leq n$_ do

4 Compute $s_{i}(z)=\mathcal{H}_{i}(q(z))$ and
$s_{j}(z)=\mathcal{H}_{j}(r(z))$

5 Compute $s_{ij}(z)=s_{i}(z)*s_{j}(z)$ using Lemma 1

6 $t^{\prime}(z)=t(z)+\mathcal{H}_{i+j}(s_{ij}(z))$

7 Set $t(z)$ as the representative polynomial of $t^{\prime}(z)$

return $t(z)$

Algorithm 3.1 Compute ($\star$) product of two polynomials

######  Lemma 2.

Let $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ be two families of subsets of $U$.
Let $\mathcal{F}$ denote the collection $\\{S_{1}\cup S_{2}|\
S_{1}\in\mathcal{F}_{1},S_{2}\in\mathcal{F}_{2}\text{ and }S_{1}\cap
S_{2}=\emptyset\\}$. Then, $p_{\psi}(\mathcal{F}_{1})\star
p_{\psi}(\mathcal{F}_{2})$ computed by Algorithm 3.1 is
$p_{\psi}(\mathcal{F})$.

###### Proof.

Define $q(z)=p_{\psi}(\mathcal{F}_{1})$, $r(z)=p_{\psi}(\mathcal{F}_{2})$ and
$t(z)=q(z)\star r(z)$. Let $S_{1}\in\mathcal{F}_{1}$ and
$S_{2}\in\mathcal{F}_{2}$ be sets such that $S_{1}\cap S_{2}=\emptyset$.
Define $S=S_{1}\cup S_{2}$ and let $\phi_{1},\phi_{2}$ and $\phi$ be the
characteristic vectors of $S_{1},S_{2}$, and $S$ respectively. We claim that
the term $z^{val(\phi)}$ is present in $t(z)$. For a vector $\phi$ and an
integer $i\in[n]$, let $\phi[i]$ denote the $i^{th}$ bit in $\phi$. As
$\phi[i]$ is 1 if and only if exactly one of the two bits $\phi_{1}[i]$,
$\phi_{2}[i]$ is 1, it follows that there is no carry at any position (and
hence no overflow) while adding $\phi_{1}$ and $\phi_{2}$. Therefore,
$\phi=\phi_{1}+\phi_{2}$ is a binary string of $n$ bits and
$\mathcal{H}(\phi)=\mathcal{H}(\phi_{1})+\mathcal{H}(\phi_{2})$. Now, as
$q(z)$ contains $z^{val(\phi_{1})}$ and $r(z)$ contains $z^{val(\phi_{2})}$,
in the execution of Algorithm 3.1, for $i=|S_{1}|$ and $j=|S_{2}|$,
polynomials $s_{i}(z)$ and $s_{j}(z)$ contain $z^{val(\phi_{1})}$ and
$z^{val(\phi_{2})}$ respectively. Step 3.1 multiplies $s_{i}(z)$ and
$s_{j}(z)$ using Fast Fourier Transformation to obtain $s_{ij}(z)$. As
$\mathcal{H}(\phi_{1})=i$, $\mathcal{H}(\phi_{2})=j$ and
$\mathcal{H}(\phi_{1})+\mathcal{H}(\phi_{2})=i+j$, $s_{ij}(z)$ contains the
term $z^{val(\phi)}=z^{val(\phi_{1})+val(\phi_{2})}$. Moreover,
$z^{val(\phi)}$ is present in $\mathcal{H}_{i+j}(s_{ij}(z))$ and hence it is a
monomial in $t(z)$ as Step 3.1 ensures that every monomial in $t(z)$ is of the
form $z^{d}$ for some integer $d$.

Next, we show that for every monomial $z^{d}$ in $t(z)$, there is a set
$S\in\mathcal{F}$ such that $d=val(\psi(S))$. Let $i$ and $j$ be integers such
that $\mathcal{H}_{i+j}(s_{ij}(z))$ contains the term $z^{d}$. As $t(z)$ was
initialized to $0$, $z^{d}$ was obtained as the product of two terms
$z^{d_{1}},z^{d_{2}}$ in $s_{i}(z)$ and $s_{j}(z)$ respectively such that
$d_{1}+d_{2}=d$. Let $S_{1}\in\mathcal{F}_{1}$ be the set such that
$\psi(S_{1})$ is the binary representation of $d_{1}$. Similarly, let
$S_{2}\in\mathcal{F}_{2}$ be the set such that $\psi(S_{2})$ is the binary
representation of $d_{2}$. Let $\phi_{1}$ and $\phi_{2}$ be the characteristic
vectors of $S_{1}$ and $S_{2}$ respectively. Then, $|S_{1}|=i$, $|S_{2}|=j$
and there is no integer $k$ between $1$ and $n$ such that
$\phi_{1}[k]=\phi_{2}[k]=1$. Therefore, $S_{1}\cap S_{2}=\emptyset$ and
$z^{d}=z^{val(S_{1}\cup S_{2})}$. Hence, the claimed set $S$ is $S_{1}\cup
S_{2}$ which is in $\mathcal{F}$ as $S_{1}\cap S_{2}=\emptyset$. ∎

######  Corollary 1.

Given a polynomial $p(z)$ of degree at most $2^{n}$, there is an algorithm
that computes $p(z)^{\ell}$ in $\mathcal{O}(2^{n}n^{3}\log n\cdot l)$ time.

###### Proof.

By Lemma 1, an execution of the Fast Fourier multiplication algorithm takes
$\mathcal{O}(2^{n}n\log n)$ time. As the for loop of Algorithm 3.1 is executed
$n^{2}$ times, the total time to compute $p(z)^{\ell}$ is
$\mathcal{O}(2^{n}n^{3}\log n)$. ∎

We now prove a result which correlates the existence of a partition of a set
with the presence of a monomial in a polynomial associated with it.

######  Lemma 3.

Consider a universe $U$ and a family $\mathcal{F}$ of its subsets with
characteristic polynomial $p(z)$. For any $W\subseteq U$, $W$ is the disjoint
union of $\ell$ sets from $\mathcal{F}$ if and only if there exists a monomial
$z^{val(\psi(W))}$ in $p(z)^{\ell}$.

###### Proof.

Let $W$ be the disjoint union of $S_{1},S_{2},\dots,S_{\ell}$ such that
$S_{i}\in\mathcal{F}$ for all $i\in[\ell]$. For any $j\in[n]$, the
$j^{\text{th}}$ bit of $\psi(W)$ is 1 if and only if there is exactly one
$S_{i}$ such that $j^{th}$ bit of $\psi(S_{i})$ is 1. Thus,
$val(\psi(W))=val(\psi(S_{1}))+val(\psi(S_{2}))+\dots+val(\psi(S_{\ell}))$.
Now, for every $S_{i}$ there is a term $z^{val(\psi(S_{i}))}$ in $p(z)$.
Further, as the $S_{i}$’s are pairwise disjoint, the monomial
$z^{val(\psi(S_{1}))}\star z^{val(\psi(S_{2}))}\star\cdots\star
z^{val(\psi(S_{\ell}))}$ which is equal to $z^{val(\psi(W))}$ is present in
$p(z)^{\ell}$.

We prove the converse by induction on $\ell$. For $\ell=1$, the statement is
vacuously true and for $\ell=2$, the claim holds from the proof of Lemma 2.
Assume that the claim holds for all the integers which are smaller than
$\ell$, that is, if there exists a monomial $z^{val(\psi(W))}$ in
$p(z)^{\ell-1}$ then $W$ can be partitioned into $\ell-1$ disjoint sets from
$\mathcal{F}$. If there exists a monomial $z^{val(\psi(W))}$ in
$p(z)^{\ell}=p(z)^{\ell-1}\star p(z)$ then it is the product of two monomials,
say $z^{val(\psi(W_{1}))}$ in $p(z)^{\ell-1}$ and $z^{val(\psi(W_{2}))}$ in
$p(z)$ respectively with $W_{1}\cap W_{2}=\emptyset$. By induction hypothesis,
$W_{1}$ is the disjoint union of $S_{1},S_{2},\dots,S_{\ell-1}$ such that
$S_{i}\in\mathcal{F}$ for all $i\in[\ell-1]$. Also, $W_{2}$ is in
$\mathcal{F}$ and since $W_{1}\cap W_{2}=\emptyset$, $S_{i}\cap
W_{2}=\emptyset$ for each $i$. Therefore, $W$ can be partitioned into sets
$S_{1},S_{2},\dots,S_{\ell-1},W_{2}$ each of which belong to $\mathcal{F}$. ∎

Now we are in a position to prove the main theorem of this section.

######  Theorem 2.

Given a graph $G$ on $n$ vertices, there is an algorithm which finds its cd-
chromatic number in $\mathcal{O}(2^{n}n^{4}\log n)$ time.

###### Proof.

Fix an arbitrary ordering on $V(G)$. With $V(G)$ as the universe, we define
the family $\mathcal{F}$ of its subsets as follows.

$\mathcal{F}:=\\{X\subseteq V(G)|\ X\text{ is an independent set and }\exists\
y\in V(G)\text{ s.t. }X\subseteq N(y)\\}$

Note that every set in $\mathcal{F}$ is an independent set and there exists a
vertex which dominates it. That is, $\mathcal{F}$ is the collection of the
possible color classes in any cd-coloring of $G$. Let $p(z)$ be the
characteristic polynomial of $\mathcal{F}$. By Lemma 3, if there exists a
monomial $z^{val(\psi(V(G)))}$ in $p(z)^{\ell}$ then $V(G)$ can be partitioned
into $\ell$ sets each belonging to $\mathcal{F}$. Hence the smallest integer
$\ell$ for which there exists a monomial $z^{val(\psi(V(G)))}$ in
$p(z)^{\ell}$ is $\chi_{cd}(G)$. By Corollary 1, $p(z)^{\ell}$ can be computed
in $\mathcal{O}(2^{n}n^{3}\log n\cdot l)$ time. As the cd-chromatic number of
a graph is upper bounded by $n$, the claimed running time bound for the
algorithm follows. ∎

##  4 FPT Algorithms for cd-Chromatic Number

Determining whether a graph $G$ has cd-chromatic number at most $q$ is -hard
on general graphs for $q\geq 4$. This implies that the cd-Coloring problem
parameterized by the number of colors is para--hard on general graphs. Thus
this necessitates the search for special classes of graphs where cd-Coloring
is . In this section we give algorithms for cd-Coloring on chordal graphs and
graphs of girth at least $5$.

We start by proving that cd-Coloring parameterized by the number of colors and
treewidth of the graph is . Towards this, we will use Courcelle’s powerful
theorem which interlinks the fixed parameter tractability of a certain graph
property with its expressibility as an MSO formula. We can write many graph
theoretical properties as an MSO formula. Following are three examples which
we will use in writing an MSO formula to check whether a graph has cd-
chromatic number at most $q$.

  * 1.

To check whether $V_{1},V_{2},\dots,V_{q}$ is a partition of $V(G)$.

${\sf Part}(V_{1},V_{2},\dots,V_{q})\equiv\forall u\in V(G)[\exists
i\in[q][(u\in V_{i})\land(\forall j\in[q][i\neq j\Rightarrow u\not\in
V_{j})]]]$

  * 2.

To check whether a given vertex set $V_{i}$ is an independent set or not.

${\sf IndSet}(V_{i})\equiv\forall u\in V_{i}[\forall v\in V_{i}[\lnot
adj(u,v)]]$

  * 3.

To check whether given vertex set $V_{i}$ is dominated by some vertex or not.

${\sf Dom}(V_{i})\equiv\exists u\in V(G)[\forall v\in V_{i}[adj(u,v)]]$

We use $\phi(G,q)$ to denote the MSO formula which states that $G$ has cd-
chromatic number at most $q$. We use the formulas defined above as macros in
$\phi(G,q)$.

$\phi(G,q)$ | $\equiv$ | $\exists V_{1},V_{2},\dots,V_{q}\subseteq V(G)[{\sf Part}(V_{1},V_{2},\dots,V_{q})\land$
---|---|---
|  |  ${\sf IndSet}(V_{1})\land\dots\land{\sf IndSet}(V_{q})\land{\sf Dom}(V_{1})\land\cdots\land{\sf Dom}(V_{q})$]

It is easy to see that the length of $\phi(G,q)$ is upper bounded by a linear
function of $q$. By applying Theorem 1 we obtain the following result.

######  Theorem 3.

cd-Coloring parameterized by the number of colors and the treewidth of the
input graph is .

###  4.1 Chordal Graphs

As the graph gets more structured, we expect many -hard problems to get
_easier_ in some sense on the restricted class of graphs having that
structure. For example, Chromatic-Coloring is -hard on general graphs but it
is polynomial time solvable on chordal graphs. However, cd-Coloring is -hard
even on the chordal graphs and we show that it is when parameterized by the
number of colors on chordal graphs.

######  Theorem 4.

cd-Coloring parameterized by the number of colors is on chordal graphs.

###### Proof.

For a chordal graph $G$, ${\mathbf{tw}}(G)=\omega(G)-1$ where $\omega(G)$ is
the size of a maximum clique in $G$ [35]. Since, a cd-coloring is also a
proper coloring, no two vertices in a clique can be in the same color class.
Thus, if $\omega(G)\geq k$ then we can conclude that $(G,k)$ is NO instance of
cd-Coloring. Otherwise, $\omega(G)\leq k$ which implies that
${\mathbf{tw}}(G)\leq k$. This bound and Theorem 3 imply that cd-Coloring
parameterized by the number of colors is on chordal graphs. ∎

###  4.2 Graphs with girth at least $5$

In this section, we show that cd-coloring on graphs of girth at least five is
with respect to the solution size as the parameter. By Observation 1, we can
assume that the input graph $G$ is connected. We can define cd-coloring of a
connected graph as a proper coloring such that every color class is contained
in the open neighbourhood of some vertex. In other words, we do not allow a
vertex to dominate itself. One can verify that the two definitions of cd-
coloring are identical on connected graphs. We now define the notion of a
total-dominating set of a graph $G$. A set $S\subseteq V(G)$ is called a
total-dominating set if $V(G)=\bigcup_{v\in S}N(v)$. That is, for every vertex
$v\in V(G)$, there exists a vertex $u\in S$, $u\neq v$, such that $v\in N(u)$.
Our interest in total-dominating set is because of its relation to cd-coloring
in graphs that do not contain triangles, that is, graphs of girth at least 4.
In particular, we need the following lemma. The first proof of this has
appeared in [21]. For the sake of completeness, we present a proof here.

######  Lemma 4 (Theorem $4$ in [21]).

If $g(G)\geq 4$, then the size of a minimum total dominating set is equal
$\chi_{cd}(G)$.

###### Proof.

Let $\phi$ be a cd-coloring of $G$ that uses $\chi_{cd}(G)$ colors and let
$V_{1},\dots,V_{q}$ be the color classes in this coloring. Then, for every
color class $V_{i}$, there is a vertex $v_{i}$ such that $V_{i}\subseteq
N(v_{i})$. Let $X$ denote the set of these vertices. Then, $X$ has at most $q$
vertices and by definition, it is a total dominating set of $G$. Hence, the
size of a minimum total dominating set of a graph is at most the cd-chromatic
number of the graph.

Suppose $X=\\{v_{1},v_{2},\dots,v_{k}\\}$ is a minimum total dominating set of
$G$. We construct a cd-coloring of $G$ using at most $k$ colors. We define the
color classes in the following way. Let $V_{1}=N(v_{1})$ and for
$i=2,\dots,k$, define $V_{i}=N(v_{i})\setminus(V_{1}\cup V_{2}\cup\dots\cup
V_{i-1})$. Note that $V_{1},\dots,V_{q}$ forms a partition of $V(G)$. Since,
$g(G)\geq 4$, it follows that each $V_{i}$ is an independent set. Furthermore,
since $X$ is a total dominating set, for each $i\in[k]$, we have a vertex
$v_{i}\in X$ such that $V_{i}\subseteq N(v_{i})$. Hence, this gives a cd-
coloring of $G$. Therefore, the cd-chromatic number of a graph is at most the
cardinality of a minimum total dominating set. Now the lemma follows by
combining the above two inequalities. ∎

Lemma 4 shows that to prove that cd-Coloring is on graphs of girth at least
four, it suffices to show that finding a total dominating set of size at most
$k$ is on these graphs. This leads to the Total Dominating Set problem. Given
a graph $G$ and an integer $k$, the Total Dominating Set problem asks whether
there exists a total dominating set of size at most $k$. Observe that we can
test whether $G$ has a total dominating set of size at most $k$ by enumerating
all subsets $S$ of $V(G)$ of size at most $k$ and checking whether any of them
forms a total-dominating set. This immediately gives an algorithm with running
time $n^{\mathcal{O}(k)}$ for cd-Coloring on graphs with girth at least $4$,
as the checking part can be done in polynomial time. It is not hard to modify
the reduction given in [36] to show that Total Dominating Set is $W[2]$ hard
on bipartite graphs. Thus, Lemma 4 implies that even cd-Coloring is $W[2]$
hard on bipartite graphs. Hence, if we need to show that cd-Coloring is , we
must assume that the girth of the input graph is at least $5$. In the rest of
this section, we show that cd-Coloring is on graphs with girth at least $5$ by
showing that Total Dominating Set is on those graphs. Before proceeding
further, we note some simple properties of graphs with girth at least $5$.

######  Observation 3.

For a graph $G$, if $g(G)\geq 5$ then for any $v$ in $V(G)$, $N(v)$ is an
independent set and for any $u,v$ in $V(G)$, $|N(v)\cap N(u)|\leq 1$.

Raman and Saurabh [36] defined a variation of Set Cover problem, namely,
Bounded Intersection Set Cover. An input to the problem consists of a universe
$\mathcal{U}$, a collection $\mathcal{F}$ of subsets of $\mathcal{U}$ and a
positive integer $k$ with the property that for any two $S_{i},S_{j}$ in
$\mathcal{F}$, $|S_{i}\cap S_{j}|\leq c$ for some constant $c$ and the
objective is to check whether there exists a sub-collection $\mathcal{F}_{0}$
of $\mathcal{F}$ of size at most $k$ such that
$\bigcup_{S\in\mathcal{F}_{0}}=\mathcal{U}$. In the same paper, the authors
proved that the Bounded Intersection Set Cover is when parameterized by the
solution size. Total Dominating Set on $(G,k)$ where $G$ has girth at least
$5$ can be reduced to Bounded Intersection Set Cover with $\mathcal{U}=V(G)$
and $\mathcal{F}=\\{N(v)|\ \forall v\in V(G)\\}$. By Observation 3, we can fix
the constant $c$ to be $1$. Hence we have the following lemma.

######  Lemma 5.

On graphs with girth at least $5$, Total Dominating Set is when parameterized
by the solution size.

We now prove that the problem has a polynomial kernel and use it to design
another algorithm.

######  Lemma 6.

Total Dominating Set admits a kernel on $\mathcal{O}(k^{3})$ vertices on the
class of graphs with girth at least 5.

###### Proof.

We start the proof with the following claim which says that every high degree
vertex should be included in every total dominating set of size at most $k$.

######  Claim 4.1.

In a graph $G$ with $g(G)\geq 5$, if there is a vertex $u$ with degree at
least $k+1$, then any total dominating set of size at most $k$ contains $u$.

###### Proof.

Suppose there exists a total dominating set $X$ of $G$ of size at most $k$
which does not contain $u$. Since $N(u)$ (having size at least $k+1$) is
dominated by $X$ and no vertex can dominate itself, by the Pigeon Hole
Principle, there exists a vertex, say $w$, in $X$ which is adjacent to at
least two vertices, say, $v_{1},v_{2}$ in $N(u)$. This implies that
$w,v_{1},v_{2},u$ form a cycle of length $4$, contradicting the fact that
girth of $G$ is at least 5. ∎

Suppose $G$ has a total dominating set of size at most $k$. Construct a tri-
partition of $V(G)$ as follows:

$\displaystyle H$ $\displaystyle=$ $\displaystyle\\{u\in V(G)~{}|~{}|N(u)|\geq
k+1\\};$ $\displaystyle J$ $\displaystyle=$ $\displaystyle\\{v\in
V(G)~{}|~{}v\notin H,~{}\exists u\in H\text{ such that }(u,v)\in E(G)\\};$
$\displaystyle R$ $\displaystyle=$ $\displaystyle V(G)\setminus(H\cup J)$

By the above claim, $H$ is contained in every total dominating set of size at
most $k$. Hence, the size of $H$ is upper bounded by $k$. Note that there is
no edge between a vertex in $H$ and a vertex in $R$. Thus, $R$ has to be
dominated by at most $k$ vertices from $J\cup R$. However, the degree of
vertices in $J\cup R$ is at most $k$ and hence $|R|\leq\mathcal{O}(k^{2})$ and
$|J\cap N(R)|$ is upper bounded by $\mathcal{O}(k^{3})$. We will now bound the
size of $J^{\star}=J\setminus N(R)$. For that, we first apply the following
reduction rule on the vertices in $J^{\star}$.

######  Reduction Rule 1.

For $u,v\in J^{\star}$, if $N(u)\cap H\subseteq N(v)\cap H$ then delete $u$.

The correctness of this reduction follows from the observation that all the
vertices in $J$ have been dominated by the vertices in $H$. The only reason
any vertex in $J^{\star}$ is part of a total dominating set is because that
vertex is used to dominate some vertex in $H$. If this is the case then the
vertex $u$ in the solution can be replaced by the vertex $v$. In the reverse
direction, if $X$ is a total dominating set of $G-\\{u\\}$ and $|X|\leq k$,
then $H\subseteq X$. Hence $u$ is dominated by $x\in X\cap H$ in $G$ too. That
is, $X$ is a total dominating set of $G$.

All that remains is to bound the size of $J^{\star}$. We partition $J^{\star}$
into two sets namely $J_{1}$ and $J_{2}$. The set $J_{1}$ is the set of
vertices which are adjacent to exactly one vertex in $H$ whereas each vertex
in $J_{2}$ is adjacent to at least two vertices in $H$. After exhaustive
application of Reduction Rule 1, no two vertices in $J_{1}$ can be adjacent to
one vertex in $H$ and hence $|J_{1}|\leq|H|\leq k$. Any vertex in $J_{2}$ is
adjacent to at least two vertices in $H$. For every vertex $u$ in $J_{2}$, we
assign a pair of vertices in $H$ to which $u$ is adjacent. By Observation 3,
no two vertices in $J_{2}$ can be assigned to the same pair and hence the size
of $J_{2}$ is upper bounded by $\binom{k}{2}\leq k^{2}$. Combining all the
bounds, we get a kernel with $\mathcal{O}(k^{3})$ vertices. ∎

Combining Lemmas 4 and 6 we obtain the following theorem.

######  Theorem 5.

On graphs with girth at least $5$, cd-Coloring admits an algorithm running in
$\mathcal{O}(2^{\mathcal{O}(q^{3})}q^{12}\log q^{3})$ time and an
$\mathcal{O}(q^{3})$ sized vertex kernel, where $q$ is number of colors.

##  5 Complexity of CD-Partization

In this section, we study the complexity of cd-Partization. As recognizing
graphs with cd-chromatic number at most $q$ is -hard on general graphs for
$q\geq 4$, the deletion problem is also -hard on general graphs for such
values of $q$. For $q=1$, the problem is trivial as $\chi_{cd}(G)=1$ if and
only if $G$ is the graph on one vertex. In this section, we show -hardness for
$q\in\\{2,3\\}$. We remark that $\mathcal{G}=\\{G\mid\chi_{cd}(G)\leq q\\}$ is
not a hereditary graph class and so the generic result of Lewis and Yannakakis
[37] does not imply the claimed -hardness.

###  5.1 Para--hardness in General Graphs

Consider the following problem.

Partization Input: Graph $G$, integers $k$ and $q$ Question: Does there exist
$S\subseteq V(G)$, $|S|\leq k$, such that $\chi(G-S)\leq q$?

Once again if $q$ is fixed, we refer to the problem as $q$-Partization.
Observe that the classical -complete problems Vertex Cover [38] and Odd Cycle
Transversal [38] are 1-Partization and 2-Partization, respectively. Now, we
proceed to show the claimed hardness.

######  Theorem 6.

$q$-cd-Partization is -complete for $q\in\\{2,3\\}$.

###### Proof.

The problem is in as determining if the cd-chromatic number of a graph is at
most $q\in\\{1,2,3\\}$ is polynomial-time solvable. Given an instance $(G,k)$
of $q$-Partization where $q\in\\{1,2\\}$, we construct the instance
$(G^{\prime},k)$ of $(q+1)$-cd-Partization as follows: $G^{\prime}$ is
obtained from $G$ by adding a new vertex $v$ adjacent to every vertex in
$V(G)$ and adding $k+q+2$ new vertices $v_{1},\cdots,v_{k+q+2}$ adjacent to
$v$. We claim that $G$ has a set of $k$ vertices whose deletion results in a
$q$-colorable graph if and only if $G^{\prime}$ has a set of $k$ vertices
whose deletion results in a $(q+1)$-cd-colorable graph.

Consider a set $S$ of $k$ vertices such that $\chi(G-S)\leq q$. Then,
$G^{\prime}-S$ is $(q+1)$-cd-colorable as a new color can be assigned to $v$
and any of the $q$ colors of $G-S$ can be assigned to
$v_{1},\cdots,v_{k+q+2}$. The color class containing $v$ is a singleton set.
This class is dominated by all vertices in $G^{\prime}-(S\setminus\\{v\\})$.
Further, $v$ dominates each of the other $q$ color classes as $v$ is a
universal vertex in $G^{\prime}$.

Conversely, let $S^{\prime}\subseteq V(G^{\prime})$ be a minimal set of at
most $k$ vertices such that $\chi_{cd}(G^{\prime}-S^{\prime})\leq q+1$. Now,
if $v\in S^{\prime}$, then vertices $v_{1},\cdots,v_{k+q+2}$ are isolated in
$G-\\{v\\}$ implying that either $|\\{v_{1},\cdots,v_{k+q+2}\\}\cap
S^{\prime}|\geq k+1$ or $\chi_{cd}(G^{\prime}-S^{\prime})>q+1$. So, we can
assume that $v\notin S^{\prime}$. Further, as $S^{\prime}$ is minimal, it
follows that $\\{v_{1},\cdots,v_{k+q+2}\\}\cap S^{\prime}=\emptyset$. Also, as
$v$ is a universal vertex in $G^{\prime}$, we have that
$\chi(G-(S^{\prime}\setminus\\{v\\}))\leq q$. So, $S^{\prime}$ is a subset of
$V(G)$ of size at most $k$ such that $G-S^{\prime}$ is $q$-colorable. ∎

###  5.2 -hardness and Fixed-Parameter Tractability in Split Graphs

A graph is a split graph if its vertex set can be partitioned into a clique
and an independent set. As split graphs are perfect (clique number is equal to
the chromatic number for every induced subgraph), we have the following
observation.

######  Observation 7.

A split graph $G$ is $r$-colorable if and only if $\omega(G)\leq r$.

The following result is known for the corresponding deletion problem.

######  Theorem 8 ([39, 40]).

Partization on Split Graphs is -complete.

This hardness was shown by a reduction from Set Cover [38]. We modify this
reduction to show that cd-Partization is -complete on split graphs. The
problem is in as the cd-chromatic coloring of a split graph can be verified in
polynomial time due to the following result.

######  Theorem 9 ([18]).

If $G$ is a connected split graph $G$, then $\omega(G)=\chi_{cd}(G)$.
Furthermore, there is an $\mathcal{O}({|V(G)|}^{2})$ time algorithm that
returns a minimum cd-coloring of $G$.

######  Theorem 10.

cd-Partization on split graphs is -hard.

###### Proof.

Consider a Set Cover instance $(U,\mathcal{F},k)$ where
$U=\\{x_{1},\cdots,x_{n}\\}$ is a finite set and $\mathcal{F}$ is a family
$\\{S_{1},\cdots,S_{m}\\}$ of subsets of $U$. The problem is to determine if
there is a collection of at most $k$ sets in $\mathcal{F}$ such that each
element of $U$ is in at least one set of the collection. The corresponding
instance of $cd$-Partization is $(G,k^{\prime}=m-k,q=k+1)$ where $G$ is a
split graph on the vertex set $C\cup
I\cup\\{w_{0},w_{1},\cdots,w_{k+k^{\prime}+2}\\}$ where $C=\\{u_{i}\mid
S_{i}\in\mathcal{F}\\}$ and $I=\\{v_{i}\mid x_{i}\in U\\}$. Also,
$(v_{i},u_{j})\in E(G)$ if and only if $x_{i}\notin S_{j}$ and $w_{0}$ is
adjacent to every vertex in $C\cup
I\cup\\{w_{1},\cdots,w_{k+k^{\prime}+2}\\}$. Further,
$I\cup\\{w_{1},\cdots,w_{k+k^{\prime}+2}\\}$ and $C$ induce an independent set
and a clique, respectively, in $G$. We claim that a set
$\mathcal{F}^{\prime}\subseteq\mathcal{F}$ of size $k$ is a set cover if and
only if $G-S^{\prime}$ is $q$-cd-colorable where $S^{\prime}=\\{u_{i}\in C\mid
S_{i}\in\mathcal{F}\setminus\mathcal{F}^{\prime}\\}$ and
$|S^{\prime}|=k^{\prime}$.

Consider a set cover $\mathcal{F}^{\prime}\subset\mathcal{F}$ of size $k$. If
there is a clique $Q$ (without loss of generality assume $w_{0}\in Q$) of size
$k+2$ in $G-S^{\prime}$, then $Q$ must contain an element $v_{i}\in I$ that is
adjacent to $k$ vertices in $C\setminus S^{\prime}$. However, since
$\mathcal{F}^{\prime}$ is a set cover, $v_{i}$ is non-adjacent to at least one
$u_{j}$ in $C\setminus S^{\prime}$ leading to a contradiction. Thus,
$S^{\prime}$ has a non-empty intersection with every $(k+2)$-clique in $G$. As
$G$ is a split graph, it is $(k+1)$-colorable due to Observation 7. Further,
$G-S^{\prime}$ is $(k+1)$-cd-colorable as the color class containing
$\\{w_{0}\\}$ is a singleton set (since it is an universal vertex) which is
dominated by itself and the other color classes are dominated by $w_{0}$.

Conversely, consider a minimal subset $S^{\prime}$ of $k^{\prime}$ vertices
such that $G-S^{\prime}$ is $(k+1)$-cd-colorable. Now, if $w_{0}\in
S^{\prime}$, then vertices $w_{1},\cdots,u_{k+k^{\prime}+2}$ are isolated in
$G-\\{w_{0}\\}$ implying that either
$|\\{w_{1},\cdots,w_{k+k^{\prime}+2}\\}\cap S^{\prime}|\geq k^{\prime}+1$ or
$\chi_{cd}(G-S^{\prime})>k+1$. So, we can assume that $w_{0}\notin
S^{\prime}$. Further, as $S^{\prime}$ is minimal, it follows that
$\\{w_{1},\cdots,w_{k+k^{\prime}+2}\\}\cap S^{\prime}=\emptyset$. Now, all
vertices in $S^{\prime}$ must belong to $C$. If there exists $v_{i}\in
S^{\prime}\cap I$, there is a clique of size $k+2$ in $G-S^{\prime}$ as $C$ is
a clique. Also, no vertex in $I$ is adjacent to all nodes in $C\setminus
S^{\prime}$ as if there is such a vertex $v_{i}$ then there is a
$(k+2)$-clique in $G-S^{\prime}$. Thus, every vertex in $I$ is nonadjacent to
at least one element in $C\setminus S^{\prime}$ implying that
$\\{s_{i}\in\mathcal{F}\mid u_{i}\in C\setminus S^{\prime}\\}$ is a set cover
of $(U,\mathcal{F})$ of size at most $k$. ∎

As Set Cover parameterized by solution size is $\W[2]$-hard [25], we have the
following result.

######  Corollary 2.

cd-Partization on split graphs parameterized by $q$ is $\W[2]$-hard.

Now, we show that the problem is $\FPT$ with respect to $q$ and $k$.

######  Theorem 11.

cd-Partization on split graphs is $\FPT$ with respect to parameters $q$ and
$k$. Furthermore, the problem does not admit a polynomial kernel unless
$\subseteq$ /poly.

###### Proof.

Compute a maximum clique $Q$ of $G$ in polynomial time. If $|Q|\leq q$, then
the input instance is an YES instance as $\chi_{cd}(G)\leq q$ from Theorem 9.
Otherwise, choose an arbitrary subset of size $q+1$ from $Q$. Since any
solution contains at least one of the $q+1$ vertices, a straightforward
branching algorithm runs in $\mathcal{O}^{*}((q+1)^{k})$ time. Now, we move on
to the kernelization hardness. Set Cover is known not to admit a polynomial
kernel when parameterized by the solution size $k^{\prime}$ and family size
$m$ as combined parameters unless $\subseteq$ /poly [25]. The reduction in
Theorem 10 produces instances of cd-Partization where solution size $k$ is
$m-k^{\prime}$ and $q$ is $k^{\prime}+1$ implying that $q+k$ is $m+1$.
Therefore, an $(q+k)^{\mathcal{O}(1)}$ kernel for cd-Partization implies an
$m^{\mathcal{O}(1)}$ kernel for Set Cover which is unlikely.

∎

##  6 Deletion to 3-cd-Colorable Graphs

In a graph $G$, an edge $e=(u,v)$ is said to be a dominating edge if $N(u)\cup
N(v)=V(G)$. Let $\overline{N[v]}$ denote the set $V(G)\setminus N[v]$. The
following characterization of 3-cd-colorable graphs is known from [18].

######  Theorem 12 ([18]).

A connected graph $G$ satisfies $\chi_{cd}(G)\leq 3$ if and only if $G$ is one
of the following types.
(Type 0) $G$ is a graph on at most 3 vertices.
(Type 1) $G$ is a bipartite graph with a dominating edge.
(Type 2) $G$ has a vertex $v$ such that $G-v$ is a bipartite graph with a
dominating edge.
(Type 3) $G$ has an ordered pair $(x,y)$ of adjacent vertices such that,

  * 1.

$V(G)=\\{x,y\\}\uplus X\uplus Y$,

  * 2.

$G[X\cup\\{y\\}]$ is a bipartite graph with at least one edge,

  * 3.

$Y\cup\\{x\\}$ is an independent set, $Y\cup\\{x\\}\subseteq N(y)$ and
$X\cup\\{y\\}\subseteq N(x)$.

(Type 4) $G$ has an ordered set $(x,y,z)$ of vertices inducing a triangle such
that,

  * 1.

$V(G)=\\{x,y,z\\}\uplus X\uplus Y\uplus Z$,

  * 2.

$X\subseteq N(x)$, $Y\subseteq N(y)$ and $Z\subseteq N(z)$,

  * 3.

$X\cup\\{y\\}$, $Y\cup\\{z\\}$ and $Z\cup\\{x\\}$ are independent sets.

(Type 5) $G$ has an ordered triple $(x,y,z)$ of vertices such that,

  * 1.

$V(G)=\\{x,y\\}\uplus X\uplus Y\uplus Z$,

  * 2.

$z\in X\cup Y$, $(x,y)\notin E(G)$ and $(x,z),(y,z)\in E(G)$,

  * 3.

$X\subseteq N(x)$, $Y\subseteq N(y)$ and $Z\subseteq N(z)$,

  * 4.

$X$, $Y$, $Z\cup\\{x\\}$ and $Z\cup\\{y\\}$ are independent sets.

We refer to the ordered sets in Types 3, 4 and 5 as dominators. In [18], they
are called as d-pair, cd-triangle and NB-triplet respectively. Now, we proceed
to solve $3$-cd-Partization. Let $G$ be the input graph on $n$ vertices, $m$
edges and $k$ be a positive integer. Consider a set $S\subseteq V(G)$ such
that $H=G-S$ is $3$-cd-colorable. Then, $H$ is of one of the types listed in
Theorem 12. Before we proceed to describe algorithms for each of these types,
we list the following well-known results on Vertex Cover and Odd Cycle
Transversal that we use in our algorithms.

######  Theorem 13 ([41]).

Given a graph $G$ and a positive integer $k$, there is an algorithm running in
$\mathcal{O}^{*}(1.2738^{k})$ time that determines if $G$ has a vertex cover
of size at most $k$ or not.

######  Theorem 14 ([42]).

Given a graph $G$ and a positive integer $k$, there is an algorithm running in
$\mathcal{O}^{*}(2.3146^{k})$ time that determines if $G$ has an odd cycle
transversal of size at most $k$ or not.

Here we use notation $\mathcal{O}^{*}$ to suppress functions which are
polynomial in size of input. As we would subsequently show, our algorithms
reduce the problem of finding an optimum deletion set into finding appropriate
vertex covers and constrained odd cycle transversals. The current best
parameterized algorithm for finding a vertex cover can straightaway be used as
a subroutine in our algorithm while the one for finding an odd cycle
transversal requires the following results. Consider a graph $G$ and let $v$
be a vertex in $G$. Define the graph $G^{\prime}$ to be the graph obtained
from $G$ by deleting $v$ and adding a new vertex $v_{ij}$ for each pair
$v_{i}$, $v_{j}$ of neighbors of $v$; further $v_{ij}$ is adjacent to $v_{i}$
and $v_{j}$.

######  Lemma 7.

$G$ has a minimal odd cycle transversal of size at most $k$ that excludes
vertex $v$ if and only if $G^{\prime}$ has a minimal odd cycle transversal of
size at most $k$.

###### Proof.

Consider an odd cycle transversal $O$ of $G$ excluding $v$ and let $(X,Y)$ be
a bipartition of $G-O$. Without loss of generality, let $v\in X$. Then, every
vertex in $N(v)$ is either in $O$ or in $Y$. Thus,
$X^{\prime}=(X\setminus\\{v\\})\cup(V(G^{\prime})\setminus V(G))$ is an
independent set in $G^{\prime}$. Consequently, $(X^{\prime},Y)$ is a
bipartition of $G^{\prime}-O$ implying that $O$ is an odd cycle transversal of
$G^{\prime}$. Conversely, any odd cycle transversal $O^{\prime}$ of
$G^{\prime}$ can be modified to one that excludes each vertex in $\\{v_{ij}\in
V(G^{\prime})\mid v_{i},v_{j}\in N(v)\\}$ without increasing the size since
any induced odd cycle through $v_{ij}$ is also an induced odd cycle through
$v_{i}$ and $v_{j}$. Then, it follows that $O^{\prime}$ is an odd cycle
transversal of $G$ that excludes $v$. ∎

Let $P,Q\subseteq V(G)$ be two disjoint sets. Let $G^{\prime\prime}$ be the
graph constructed from $G$ by adding an independent set $I_{P}$ of $k+1$ new
vertices each of which is adjacent to every vertex in $P$ and an independent
set $I_{Q}$ of $k+1$ new vertices each of which is adjacent to every vertex in
$Q$. Further, every vertex in $I_{P}$ is adjacent to every vertex in $I_{Q}$.

######  Lemma 8.

$G$ has a minimal odd cycle transversal $O$ of size at most $k$ such that
$G-O$ has a bipartition $(X,Y)$ with $P\subseteq X$ and $Q\subseteq Y$ if and
only if $G^{\prime\prime}$ has a minimal odd cycle transversal of size at most
$k$.

###### Proof.

Suppose $G-O$ has a bipartition $(X,Y)$ such that $P\subseteq X$ and
$Q\subseteq Y$. Then, $G^{\prime\prime}-O$ has a bipartition
$(X^{\prime},Y^{\prime})$ where $X^{\prime}=X\cup I_{Q}$ and $Y^{\prime}=Y\cup
I_{P}$. Thus, $O$ is an odd cycle transversal of $G^{\prime\prime}$ too.
Conversely, consider a minimal odd cycle transversal $O^{\prime}$ of size $k$
of $G^{\prime\prime}$. Clearly, $O^{\prime}$ excludes at least one vertex $a$
from $I_{P}$ and at least one vertex $b$ from $I_{Q}$. Consider an arbitrary
bipartition $(A,B)$ of $G^{\prime\prime}-O^{\prime}$ and let $a\in A$ and
$b\in B$. Then, as $O^{\prime}$ is minimal $I_{P}\subseteq A$ and
$I_{Q}\subseteq B$. That is, $O^{\prime}\cap(I_{P}\cup I_{Q})=\emptyset$.
Further, as any two vertices $p\in I_{P}$ and $q\in I_{Q}$ are adjacent,
$I_{P}\cap V(G^{\prime\prime}-O^{\prime})\subseteq A$ and $I_{Q}\cap
V(G^{\prime\prime}-O^{\prime})\subseteq B$. Thus, $P\subseteq B$ and
$Q\subseteq A$. ∎

###  6.1 Deletion to Types 0, 1 and 2

It is trivial to check if $G$ has a solution whose deletion results in a graph
$H$ with at most 3 vertices. So, deletion to Type 0 is easy. Now, suppose $H$
is of Type 1. Then, we need to identify an edge of $G$ that is a dominating
edge for $H$. We describe an algorithm based on this observation.

Input : A graph $G$ and a positive integer $k$.

Output : $S\subseteq V(G)$, $|S|\leq k$ such that $G-S$ is of Type 1 (if one
exists).

1

32for  _each edge $(x,y)$ in $G$_ do

4 Let $X^{\prime}=N(x)\cap\overline{N[y]}$ and
$Y^{\prime}=N(y)\cap\overline{N[x]}$.

5 Let $S^{\prime}$ be $V(G)\setminus(X^{\prime}\cup Y^{\prime})$ and decrease
$k$ by $|S^{\prime}|$.

7 6 for  _each $k_{1}$ and $k_{2}$ such that $k_{1}+k_{2}\leq k$_ do

9 8 Compute a vertex cover $S_{1}$ of $G[X^{\prime}]$ with $|S_{1}|\leq k_{1}$
(if one exists).

10 /* $(X^{\prime}\setminus S_{1})\cup\\{y\\}$ is an independent set */

12 11 Compute a vertex cover $S_{2}$ of $G[Y^{\prime}]$ with $|S_{2}|\leq
k_{2}$ (if one exists).

13 /* $(Y^{\prime}\setminus S_{2})\cup\\{x\\}$ is an independent set */

14 if  _$S_{1}$ and $S_{2}$ are non-empty sets_ then

15 return _$S^{\prime}\cup S_{1}\cup S_{2}$ _

16

17

Algorithm 6.1 Deletion-to-Type1$(G,k)$

######  Lemma 9.

Algorithm 6.1 runs in $\mathcal{O}^{*}(1.2738^{k})$ time.

###### Proof.

The outer loop (step 1) is executed at most $m$ times (once for each edge) and
the inner loop (step 2) is executed at most $k^{2}$ times. Let $(x,y)$ be an
edge in $G$. We need to extend $\\{x\\}$ and $\\{y\\}$ into independent sets
$Y$ and $X$ respectively, such that $X$ is dominated by $x$ and $Y$ is
dominated by $y$. Clearly, neighbors of $x$ and non-neighbors of $y$ cannot be
in $Y$. Similarly, neighbors of $y$ and non-neighbors of $x$ cannot be in $X$.
No common neighbor of $x$ and $y$ can be in either $X$ or $Y$. Thus, the
candidates for $X$ and $Y$ are $X^{\prime}=N(x)\cap\overline{N[y]}$ and
$Y^{\prime}=N(y)\cap\overline{N[x]}$ respectively. All vertices in
$V(G)\setminus(X^{\prime}\cup Y^{\prime})$ are in any solution. Let
$k^{\prime}=k-|V(G)\setminus(X^{\prime}\cup Y^{\prime})|$. Then, $G$ has a
$3$-cd-partization solution $S$ of size at most $k$ such that $G-S$ is of Type
1 with $(u,v)$ as a dominating edge if and only if there exists integers
$k_{1}$, $k_{2}$ with $k_{1}+k_{2}\leq k^{\prime}$ such that $G[X^{\prime}]$
has a vertex cover of size at most $k_{1}$ and $G[Y^{\prime}]$ has a vertex
cover of size at most $k_{2}$. Now, Steps 3 and 4 take
$\mathcal{O}^{*}(1.2738^{k})$ time from Theorem 13. Thus, the overall running
time is $\mathcal{O}^{*}(1.2738^{k})$. ∎

Suppose $H$ is of Type 2. Then, for each vertex $v$ of $G$, we simply run
Algorithm 6.1 on $G-\\{v\\}$ with parameter $k$.

Input : A graph $G$ and a positive integer $k$.

Output : $S\subseteq V(G)$, $|S|\leq k$ such that $G-S$ is of Type 2 (if one
exists).

1

32for  _each vertex $x$ in $G$_ do

4 Deletion-to-Type1$(G-\\{x\\},k)$.

5

Algorithm 6.2 Deletion-to-Type2$(G,k)$

######  Lemma 10.

Algorithm 6.2 runs in $\mathcal{O}^{*}(1.2738^{k})$ time.

###### Proof.

As Algorithm 6.2 calls Algorithm 6.1 at most $n$ times, its running time is
$\mathcal{O}^{*}(1.2738^{k})$. ∎

###  6.2 Deletion to Type 3

Suppose $H$ is of Type 3 with dominator $(x,y)$. Then, the following holds.

######  Observation 15 ([18]).

$\overline{N_{H}[x]}$ is an independent set and $\overline{N_{H}[x]}\subseteq
N_{H}(y)$. Further, $N_{H}(x)$ induces a bipartite graph with at least one
edge.

This observation leads to the following algorithm.

Input : A graph $G$ and a positive integer $k$.

Output : $S\subseteq V(G)$, $|S|\leq k$ such that $G-S$ is of Type 3 (if one
exists).

1

32for  _each ordered pair $(x,y)$ of adjacent vertices in $G$_ do

4 Let $Y^{\prime}=N(y)\cap\overline{N[x]}$ and $X^{\prime}=N(x)$.

5 Let $S^{\prime}$ be $V(G)\setminus(X^{\prime}\cup Y^{\prime})$ and decrease
$k$ by $|S^{\prime}|$.

7 6 for  _each $k_{1}$ and $k_{2}$ such that $k_{1}+k_{2}\leq k$_ do

9 8 Compute a vertex cover $S_{1}$ of $G[Y^{\prime}]$ with $|S_{1}|\leq k_{1}$
(if one exists).

10 /* $(Y^{\prime}\setminus S_{1})\cup\\{x\\}$ is an independent set */

12 11 Compute a minimal odd cycle transversal $S_{2}$ of at most $k_{2}$
vertices (if one exists) in $G[X^{\prime}]$ such that $y\notin S_{2}$.

13 if  _$S_{1}$ and $S_{2}$ are non-empty sets_ then

14 return _$S^{\prime}\cup S_{1}\cup S_{2}$ _

15

16

Algorithm 6.3 Deletion-to-Type3$(G,k)$

######  Lemma 11.

Algorithm 6.3 runs in $\mathcal{O}^{*}(2.3146^{k})$ time.

###### Proof.

The outer loop (step 1) is executed at most $2m$ times (as there are two
ordered pairs for each edge) and the inner loop (step 2) is executed at most
$k^{2}$ times. Consider an edge $(x,y)$ in $G$. If $(x,y)$ is a dominator in
$H$, then we need to extend $\\{x\\}$ into an independent set $Y$ that is
dominated by $y$ and extend $\\{y\\}$ into an induced bipartite graph $B$
(with at least one edge) such that $V(B)$ is dominated by $x$. Observe that
$Y$ contains only neighbors of $y$ and $V(B)$ contains only neighbors of $x$.
Further, a neighbor of $y$ that is not adjacent to $x$ cannot be in $V(B)$ and
a neighbor of $y$ that is adjacent to $x$ cannot be in $Y$. Thus, the
candidates for $V(B)$ and $Y$ are $X^{\prime}=N(x)$ and
$Y^{\prime}=N(y)\cap\overline{N[x]}$ respectively. All vertices in
$V(G)\setminus(X^{\prime}\cup Y^{\prime})$ are in any solution. Let
$k^{\prime}=k-|V(G)\setminus(X^{\prime}\cup Y^{\prime})|$. Now, $G$ has a
$3$-cd-partization solution $S$ of size at most $k$ such that $G-S$ is of Type
3 with $(x,y)$ as a dominator if and only if there exists integers $k_{1}$ and
$k_{2}$ with $k_{1}+k_{2}\leq k^{\prime}$ such that $G[Y^{\prime}]$ has a
vertex cover of size at most $k_{1}$ and $G[X^{\prime}]$ has an odd cycle
transversal of size $k_{2}$ not containing $y$ such that the resultant
bipartite graph is non-edgeless. Clearly step 3 takes
$\mathcal{O}^{*}(1.2738^{k})$ time. For step 4, we need to find a minimal odd
cycle transversal that excludes vertex $y$. We construct a graph $G^{\prime}$
obtained from $G[X^{\prime}]$ by deleting $y$ and adding a new vertex $y_{ij}$
for each pair $y_{i}$, $y_{j}$ of neighbors of $y$; further $y_{ij}$ is
adjacent to $y_{i}$ and $y_{j}$. From Lemma 7, we have that $G[X^{\prime}]$
has a minimal odd cycle transversal of size at most $k_{2}$ not containing $y$
if and only if $G^{\prime}$ has a minimal odd cycle transversal of size at
most $k_{2}$. Now, by using Theorem 14, it follows that step 4 takes
$\mathcal{O}^{*}(2.3146^{k})$ time and this gives us the claimed running time
of the algorithm. ∎

###  6.3 Deletion to Type 4

Suppose $H$ is of Type 4 and has $(x,y,z)$ as a dominator. Then, we have the
following observation.

######  Observation 16 ([18]).

$N_{H}(x)\cap N_{H}(y)\cap N_{H}(z)=\emptyset$ and
$\overline{N_{H}[x]}\cap\overline{N_{H}[y]}\cap\overline{N_{H}[z]}=\emptyset$.
Further, $X=N_{H}(x)\cap\overline{N_{H}[y]}$,
$Y=N_{H}(y)\cap\overline{N_{H}[z]}$ and $Z=N_{H}(z)\cap\overline{N_{H}[x]}$.

Now, we have the following algorithm.

Input : A graph $G$ and a positive integer $k$

Output : $S\subseteq V(G)$, $|S|\leq k$ such that $G-S$ is of Type 4 (if one
exists)

1

32for  _each ordered triple $(x,y,z)$ of pairwise adjacent vertices of $G$_ do

4 Let $X^{\prime}=N(x)\cap\overline{N[y]}$,
$Y^{\prime}=N(y)\cap\overline{N[z]}$ and $Z^{\prime}=N(z)\cap\overline{N[x]}$.

5 Let $S^{\prime}$ be $V(G)\setminus(X^{\prime}\cup Y^{\prime}\cup
Z^{\prime})$ and decrease $k$ by $|S^{\prime}|$.

7 6 for  _each $k_{1}$, $k_{2}$ and $k_{3}$ such that $k_{1}+k_{2}+k_{3}\leq
k$_ do

9 8 Compute a vertex cover $S_{1}$ of $G[X^{\prime}]$ with $|S_{1}|\leq k_{1}$
(if one exists).

10 /* $(X^{\prime}\setminus S_{1})\cup\\{y\\}$ is an independent set */

12 11 Compute a vertex cover $S_{2}$ of $G[Y^{\prime}]$ with $|S_{2}|\leq
k_{2}$ (if one exists).

13 /* $(Y^{\prime}\setminus S_{2})\cup\\{z\\}$ is an independent set */

15 14 Compute a vertex cover $S_{3}$ of $G[Z^{\prime}]$ with $|S_{3}|\leq
k_{3}$ (if one exists).

16 /* $(Z^{\prime}\setminus S_{3})\cup\\{x\\}$ is an independent set */

17 if  _$S_{1}$ , $S_{2}$ and $S_{3}$ are non-empty sets_ then

18 return _$S^{\prime}\cup S_{1}\cup S_{2}\cup S_{3}$ _

19

20

Algorithm 6.4 Deletion-to-Type4$(G,k)$

######  Lemma 12.

Algorithm 6.4 runs in $\mathcal{O}^{*}(1.2738^{k})$ time.

###### Proof.

The outer loop (step 1) is executed at most $n^{3}$ times and the inner loop
(step 2) is executed at most $k^{3}$ times. Consider a triangle $\\{x,y,z\\}$
in $G$. If $(x,y,z)$ is a dominator in $H$, then we need to extend $\\{x\\}$,
$\\{y\\}$, $\\{z\\}$ into independent sets $Y$, $Z$, $X$ dominated by $y$, $z$
and $x$ respectively. Thus, the candidates for $X$, $Y$ and $Z$ are sets
$X^{\prime}=N(x)\cap\overline{N[y]}$, $Y^{\prime}=N(y)\cap\overline{N[z]}$ and
$Z^{\prime}=N(z)\cap\overline{N[x]}$. All vertices in
$S^{\prime}=V(G)\setminus(X^{\prime}\cup Y^{\prime}\cup Z^{\prime})$ are in
any solution. Let $k^{\prime}=k-|V(G)\setminus S^{\prime}|$. Then, $G$ has a
$3$-cd-partization solution $S$ of size at most $k$ such that $G-S$ is of Type
4 with $(x,y,z)$ as a dominator if and only if there exists integers $k_{1}$,
$k_{2}$ and $k_{3}$ with $k_{1}+k_{2}+k_{3}\leq k^{\prime}$ such that
$G[Y^{\prime}]$ has a vertex cover of size at most $k_{1}$, $G[Z^{\prime}]$
has a vertex cover of size at most $k_{2}$ and $G[Z^{\prime}]$ has a vertex
cover of size at most $k_{3}$. Steps 3, 4 and 5 take
$\mathcal{O}^{*}(1.2738^{k})$ time from Theorem 13 and the overall running
time is $\mathcal{O}^{*}(1.2738^{k})$. ∎

###  6.4 Deletion to Type 5

Suppose $H$ is of Type 5 and has $(x,y,z)$ as a dominator. Then, we have the
following observation.

######  Observation 17 ([18]).

$\overline{N_{H}[x]}\cap\overline{N_{H}[y]}$ is an independent set. Further,
$z\in N_{H}(x)\cup N_{H}(y)$ and
$\overline{N_{H}[x]}\cap\overline{N_{H}[y]}\subseteq N_{H}(z)$. Moreover, in
$G-Z$, $N[x]\cup N[y]=V(G-Z)$, $N(x)\setminus N(y)\subseteq X$ and
$N(y)\setminus N(x)\subseteq Y$.

Now, we have the following algorithm.

Input : A graph $G$ and a positive integer $k$

Output : $S\subseteq V(G)$, $|S|\leq k$ such that $G-S$ is of Type 5 (if one
exists)

1

32for  _each ordered triple $(x,y,z)$ of vertices of $G$ such that
$(x,y)\notin E(G)$ and $(x,z),(y,z)\in E(G)$_ do

4 Let $Z^{\prime}$ be the set $N(z)\cap(\overline{N[y]}\cap\overline{N[x]})$.

5 Let $S^{\prime}$ be $(N(y)\cap N(z))\setminus N(x)$.

6 Let $B^{\prime}$ be the set $\\{z\\}\cup(((N(x)\cup N(y))\setminus
S^{\prime})$.

7 Let $S^{\prime\prime}$ be $V(G)\setminus(Z^{\prime}\cup B^{\prime})$ and
decrease $k$ by $|S^{\prime\prime}|$.

9 8 for  _each $k_{1}$ and $k_{2}$ such that $k_{1}+k_{2}\leq k$_ do

11 10 Compute a vertex cover $S_{1}$ of $G[Z^{\prime}]$ with $|S_{1}|\leq
k_{1}$ (if one exists).

12 /* $(Z^{\prime}\setminus S_{1})\cup\\{x,y\\}$ is an independent set */

14 13 Compute a minimal odd cycle transversal $S_{2}$ of $G[B^{\prime}]$ with
$|S_{2}|\leq k_{2}$ not containing $z$ (if one exists) such that the resultant
bipartite graph has a bipartition $(X,Y)$ such that $X\subseteq N(x)$,
$Y\subseteq N(y)$ and $z\in Y$.

15 if  _$S_{1}$ and $S_{2}$ are non-empty sets_ then

16 return _$S^{\prime\prime}\cup S_{1}\cup S_{2}$ _

17

18

Algorithm 6.5 Deletion-to-Type5$(G,k)$

######  Lemma 13.

Algorithm 6.5 runs in $\mathcal{O}^{*}(2.3146^{k})$ time.

###### Proof.

Consider an ordered triple $(x,y,z)$ of vertices in $G$. If $(x,y,z)$ is a
dominator in $H$, then we need to extend $\\{x,y\\}$ into an independent set
$Z$ that is dominated by $z$ and extend $\\{z\\}$ into a bipartite graph $B$
with bipartition $(X,Y)$ such that $X$ is dominated by $x$ and $Y$ is
dominated by $y$. Thus, the candidates for $Z$ and $V(B)$ are
$Z^{\prime}=N(z)\cap(\overline{N[y]}\cap\overline{N[x]})$ and
$B^{\prime}=\\{z\\}\cup((N(x)\cup N(y))\setminus(N(y)\cap N(z))\setminus
N(x))$ respectively. All vertices in $V(G)\setminus(Z^{\prime}\cup
B^{\prime})$ are in any solution. Let
$k^{\prime}=k-|V(G)\setminus(Z^{\prime}\cup B^{\prime})|$. Then, $G$ has a
$3$-cd-partization solution $S$ of size at most $k$ such that $H=G-S$ is of
Type 5 with $(x,y,z)$ as a dominator if and only if there exists integers
$k_{1}$ and $k_{2}$ with $k_{1}+k_{2}\leq k^{\prime}$ such that
$G[Z^{\prime}]$ has a vertex cover of size at most $k_{1}$ and $G[B^{\prime}]$
has an odd cycle transversal of size $k_{2}$ not containing $z$ such that the
resultant bipartite graph has a bipartition $(X,Y)$ such that $X\subseteq
N(x)$, $Y\subseteq N(y)$ and $z\in Y$. Step 3 takes
$\mathcal{O}^{*}(1.2738^{k})$ time. For step 4, we use Lemmas 7 and 8. Let
$G^{\prime}$ be the graph obtained from $G[B^{\prime}]$ by deleting $z$ and
adding a new vertex $z_{ij}$ for each pair $z_{i}$, $z_{j}$ of neighbors of
$z$, adjacent to $z_{i}$ and $z_{j}$. Now, a minimal odd cycle transversal of
$G^{\prime}$ corresponds to a minimal odd cycle transversal of $G[B^{\prime}]$
not containing $z$. However, we also need the additional constraint that such
an odd cycle transversal results in a bipartite graph $B$ which has a
bipartition $(X,Y)$ such that $X\subseteq N(x)$ and $Y\subseteq N(y)$. The
possible vertices in $B$ are from the set $\\{z\\}\cup(((N(x)\cup
N(y))\setminus(N(y)\cap N(z))\setminus N(x))$. The following observations on
vertices from this set are easy to verify.

  * 1.

$N_{x}=N(x)\setminus(N(y)\cup N(z))$ cannot be dominated by $y$ and
$N_{y}=N(y)\setminus(N(x)\cup N(z))$ cannot be dominated by $x$.

  * 2.

$N_{zx}=(N(x)\cap N(z))\setminus N(y)$ and $N_{xyz}=N(x)\cap N(y)\cap N(z)$
cannot be in a part of the bipartition that contains $z$.

It follows that we need an odd cycle transversal (of size at most $k_{2}$) of
$G[B^{\prime}]$ after deleting which the resultant bipartite graph has a
2-coloring in which any vertex from $P=\\{z\\}\cup N_{y}$ receives color 1 and
any vertex from $Q=N_{x}\cup N_{zx}\cup N_{xyz}$ receives color 2. This is
achieved by constructing graph $G^{\prime\prime}$ from $G^{\prime}$ by adding
an independent set $I_{P}$ of $k_{2}+1$ new vertices each of which is adjacent
to every vertex in $P$ and an independent set $I_{Q}$ of $k_{2}+1$ new
vertices each of which is adjacent to every vertex in $Q$. Further, every
vertex in $I_{P}$ is adjacent to every vertex in $I_{Q}$. Now, $G[B^{\prime}]$
has a minimal odd cycle transversal of size at most $k_{2}$ not containing $z$
such that the resultant bipartite graph has a bipartition $(X,Y)$ such that
$X\subseteq N(x)$, $Y\subseteq N(y)$ and $z\in Y$ if and only if
$G^{\prime\prime}$ has a minimal odd cycle transversal of size at most
$k_{2}$. Now, using Theorem 14, it follows that step 4 takes
$\mathcal{O}^{*}(2.3146^{k})$ time and the overall running time is dominated
(upto polynomial factors) by this computation. ∎

From Lemmata 9, 10, 11, 12 and 13, we have the following result.

######  Theorem 18.

Given a graph $G$ and an integer $k$, there is an algorithm that determines if
there is a set $S$ of size $k$ whose deletion results in a graph $H$ with
$\chi_{cd}(H)\leq 3$ in $\mathcal{O}^{*}(2.3146^{k})$ time.

##  7 Concluding Remarks

In this work, we described exact and algorithms for problems associated with
cd-coloring. We also explored the complexity of finding the cd-chromatic
number in graphs of girth at least $5$ and chordal graphs. On the former graph
class, we described a polynomial kernel. The kernelization complexity on other
graph classes and whether the problem is parameterized by only treewidth are
natural directions for further study. It is also interesting to get an exact
function when parameterized by treewidth and the number of colors.

## References

  * [1] A. Björklund, T. Husfeldt, M. Koivisto, Set Partitioning via Inclusion-Exclusion, SIAM J. Comput. 39 (2) (2009) 546–563.
  * [2] S. Gaspers, D. Kratsch, M. Liedloff, I. Todinca, Exponential Time Algorithms for the Minimum Dominating Set Problem on Some Graph Classes, ACM Trans. Algorithms 6 (1) (2009) 9:1–9:21.
  * [3] S. Gaspers, M. Liedloff, A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set, Discrete Mathematics & Theoretical Computer Science 14 (1) (2012) 29–42.
  * [4] D. Kratsch, Exact Algorithms for Dominating Set, in: Encyclopedia of Algorithms, Springer, 2008, pp. 284–286.
  * [5] E. Lawler, A Note on the Complexity of the Chromatic Number Problem, Information Processing Letters 5 (3) (1976) 66–67.
  * [6] J. M. M. van Rooij, H. L. Bodlaender, Exact Algorithms for Dominating Set, Discrete Applied Mathematics 159 (17) (2011) 2147–2164.
  * [7] A. Blum, D. R. Karger, An $\tilde{\mathcal{O}}(n^{3/14})$-coloring Algorithm for $3$-colorable Graphs, Inf. Process. Lett. 61 (1) (1997) 49–53.
  * [8] S. Guha, S. Khuller, Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating Sets, Inf. Comput. 150 (1) (1999) 57–74.
  * [9] D. Kim, Z. Zhang, X. Li, W. Wang, W. Wu, D. Z. Du, A Better Approximation Algorithm for Computing Connected Dominating Sets in Unit Ball Graphs, IEEE Transactions on Mobile Computing 9 (8) (2010) 1108–1118.
  * [10] C. Lenzen, R. Wattenhofer, Minimum Dominating Set Approximation in Graphs of Bounded Arboricity, in: Distributed Computing, 24th International Symposium, DISC 2010, 2010, pp. 510–524.
  * [11] J. Alber, H. L. Bodlaender, H. Fernau, T. Kloks, R. Niedermeier, Fixed Parameter Algorithms for Dominating Set and Related Problems on Planar Graphs, Algorithmica 33 (4) (2002) 461–493.
  * [12] N. Alon, S. Gutner, Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs, Algorithmica 54 (4) (2009) 544–556.
  * [13] L. Cai, Parameterized Complexity of Vertex Colouring, Discrete Applied Mathematics 127 (3) (2003) 415–429.
  * [14] R. G. Downey, M. R. Fellows, C. McCartin, F. A. Rosamond, Parameterized Approximation of Dominating Set Problems, Inf. Process. Lett. 109 (1) (2008) 68–70.
  * [15] R. Gera, C. Rasmussen, S. Horton, Dominator Colorings and Safe Clique Partitions, Congressus Numerantium 181 (7-9) (2006) 19–32.
  * [16] R. Gera, On Dominator Colorings in Graphs, Graph Theory Notes of New York LII (2007) 25–30.
  * [17] M. Chellali, F. Maffray, Dominator Colorings in Some Classes of Graphs, Graphs and Combinatorics 28(1) (2012) 97–107.
  * [18] M. A. Shalu, T. P. Sandhya, The cd-coloring of Graphs, in: International Conference on Algorithms and Discrete Applied Mathematics, 2016, pp. 337–348.
  * [19] Y. B. Venkatakrishnan, V. Swaminathan, Color Class Domination Number of Middle Graph and Center Graph of K1,n, Cn, Pn, Advanced Modeling and Optimization 12 (2010) 233–237.
  * [20] A. M. Abid, T. R. Rao, Dominated coloring of mycielskian graphs, International Journal of Pure and Applied Mathematics 119 (13) (2018) 21–29.
  * [21] H. B. Merouane, M. Haddad, M. Chellali, H. Kheddouci, Dominated colorings of graphs, Graphs and combinatorics 31 (3) (2015) 713–727.
  * [22] M. Shalu, S. Vijayakumar, T. Sandhya, A lower bound of the cd-chromatic number and its complexity, in: Conference on Algorithms and Discrete Applied Mathematics, Springer, 2017, pp. 344–355.
  * [23] M. Shalu, S. Vijayakumar, T. Sandhya, On the complexity of cd-coloring of graphs, Discrete Applied Mathematics 280 (2020) 171–185.
  * [24] F. Choopani, A. Jafarzadeh, A. Erfanian, D. A. Mojdeh, On dominated coloring of graphs and some nordhaus–gaddum-type relations, Turkish Journal of Mathematics 42 (5) (2018) 2148–2156.
  * [25] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, S. Saurabh, Parameterized Algorithms, Springer-Verlag, 2015.
  * [26] R. G. Downey, M. R. Fellows, Fundamentals of Parameterized Complexity, Springer-Verlag London, 2013.
  * [27] J. Flum, M. Grohe, Parameterized Complexity Theory, Springer, 2006.
  * [28] R. Niedermeier, Invitation to Fixed Parameter Algorithms, Oxford University Press, USA, 2006.
  * [29] V. V. Lozin, M. Kaminski, Coloring Edges and Vertices of Graphs Without Short or Long Cycles, Contributions to Discrete Mathematics 2 (1) (2007) 61–66.
  * [30] R. Diestel, Graph Theory, Springer-Verlag Berlin Heidelberg, 2006.
  * [31] B. Courcelle, The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs, Inf. Comput. 85 (1) (1990) 12–75.
  * [32] B. Courcelle, The Monadic Second-order Logic of Graphs III: Tree-decompositions, Minor and Complexity Issues, ITA 26 (1992) 257–286.
  * [33] F. Panolan, G. Philip, S. Saurabh, B-Chromatic Number: Beyond NP-Hardness, in: 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, 2015, pp. 389–401.
  * [34] D. D. A. Schönhage, V. Strassen, Schnelle Multiplikation Grosser Zahlen, Computing 7 (3-4) (1971) 281–292.
  * [35] M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Second Edition, Elsevier Science B.V., 2004.
  * [36] V. Raman, S. Saurabh, Short Cycles Make W-hard Problems Hard: FPT Algorithms for W-hard Problems in Graphs With No Short Cycles, Algorithmica 52 (2) (2008) 203–225.
  * [37] J. M. Lewis, M. Yannakakis, The Node-Deletion Problem for Hereditary Properties is NP-Complete, Journal of Computer and System Sciences 20 (2) (1980) 219–230.
  * [38] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H.Freeman and Company, 1979.
  * [39] D. G. Corneil, J. Fonlupt, The Complexity of Generalized Clique Covering, Discrete Applied Mathematics 22 (2) (1989) 109–118.
  * [40] M. Yannakakis, F. Gavril, The Maximum $k$-colorable Subgraph Problem for Chordal Graphs, Information Processing Letters 24 (2) (1987) 133–137.
  * [41] J. Chen, I. Kanj, G. Xia, Improved Upper Bounds for Vertex Cover, Theoretical Computer Science 411 (40-42) (2010) 3736–3756.
  * [42] D. Lokshtanov, N. S. Narayanaswamy, V. Raman, M. S. Ramanujan, S. Saurabh, Faster Parameterized Algorithms Using Linear Programming, ACM Trans. Algorithms 11 (2) (2014) 15:1–15:31.