# Colouring a Dominating Set without Conflicts:
$q$-Subset Square Colouring

V P Abidha 111First author is supported by the TCS Research scholar program.
<EMAIL_ADDRESS>Pradeesha Ashok<EMAIL_ADDRESS>Avi Tomar
<EMAIL_ADDRESS>Dolly Yadav<EMAIL_ADDRESS>International
Institute of Information Technology Bangalore, India

###### Abstract

The _Square Colouring_ of a graph $G$ refers to colouring of vertices of a
graph such that any two distinct vertices which are at distance at most two
receive different colours. In this paper, we initiate the study of a related
colouring problem called the _subset square colouring_ of graphs. Broadly, the
subset square colouring of a graph studies the square colouring of a
dominating set of a graph using $q$ colours. Here, the aim is to optimize the
number of colours used. This also generalizes the well-studied Efficient
Dominating Set problem. We show that the $q$-Subset Square Colouring problem
is NP-hard for all values of $q$ even on bipartite graphs and chordal graphs.
We further study the parameterized complexity of this problem when
parameterized by a number of structural parameters. We further show bounds on
the number of colours needed to subset square colour some graph classes.

###### keywords:

Graph colouring , Square colouring , Subset Square Colouring , Parameterized
algorithm , Dominating set

##  1 Introduction

Vertex colouring is an important problem in the area of graph theory. For a
graph $G(V,E)$, the vertex colouring of $G$ refers to a function $f$ from the
vertex set $V$ to a set of colours. There are different types of graph
colouring problems based on the constraints imposed on this function. A very
popular graph colouring question is the Proper Colouring where any two
adjacent vertices are to be assigned different colours. Also, several other
variants of vertex colouring exist, like harmonious colouring, sigma
colouring, metric colouring and acyclic colouring. In addition to the
theoretical interest, graph colouring problems are motivated by applications
in various fields like register allocation in compilers, job scheduling,
transportation networks, etc. See [13] for a detailed reading of graph
colouring. ††A primary version of this paper appeared in International
Computer Science Symposium in Russia(CSR)2022 [2].

A number of graph colouring problems are motivated by a problem in
Communication called the _Channel Allocation_ problem. Here, there exist
transmitters $v_{1},v_{2},\dots,v_{n}$ and a transmitter may interfere with
another transmitter due to a number of reasons. Now the goal is to assign
frequencies to the transmitters such that clear reception of signals is
guaranteed. This can be represented as a graph where every vertex corresponds
to a transmitter and the interference between transmitters is captured by the
distance between the corresponding vertices in the graph. Here the frequency
assigned to a transmitter corresponds to the colour assigned to the
corresponding vertex. In the 90s, Griggs and Yeh [24] introduced a concept of
assigning colours (equivalently, non-negative integers) to vertices such that
the assignment of colours to any two vertices depends on whether they are at
distance at most two. This is called the $L(h,k)$-colouring of graphs. A
colouring $c$ of graph $G$ is an $L(h.k)$-colouring if for any two vertices
$u,v\in V(G)$, $|c(u)-c(v)|\geq h$ if $u$ and $v$ are at distance $1$ and
$|c(u)-c(v)|\geq k$ if $u$ and $v$ are at distance $2$. Thus, $L(1,0)$\-
colouring is the proper colouring itself. Other versions of this problem based
on different values of $h$ and $k$ are well-studied [12]. Note that
$L(1,1)$-colouring involves colouring of vertices with non-negative integers
such that the colours on adjacent vertices differ by at least $1$ and the
colours on vertices at distance $2$ also differ by at least $1$. This graph
colouring is also referred to as _Square colouring_ [11, 25] since it is
equivalent to the proper colouring of the square of a graph.

We initiate the study of a variant of Square colouring called subset square
colouring. This is defined as follows:

###### Definition 1

Let $G=(V,E)$ be an undirected graph. A colouring function
$c:V(G)\rightarrow\\{c_{0},c_{1},\cdots,c_{q}\\}$ is called a _$q$ -subset
square colouring_ of $G$ if it satisfies the following constraints:

  * 1.

For every vertex $v$ and every colour $c_{i},1\leq i\leq q$, we have
$|c^{-1}(c_{i})\cap N[v]|\leq 1$.

  * 2.

A vertex $v$ can have at most $deg(v)$ vertices with colour $c_{0}$ in $N[v]$,
where $deg(v)$ refers to degree of $v$.

The open neighbourhood $N(v)$ of the vertex $v$ consists of the set of
vertices adjacent to $v$, i.e., $N(v)=\\{u\in V|(u,v)\in E\\}$, and the closed
neighbourhood of $v$ is $N[v]=\\{v\\}\cup N(v)$.

Here, intuitively, assigning the colour $c_{0}$ to a vertex $v$ corresponds to
$v$ being uncoloured. In this paper, we refer to a vertex being uncoloured and
a vertex coloured $c_{0}$, interchangably. Similarly a vertex is said to be
coloured if it is coloured using one of the colours from the set
$\\{c_{1}\cdots c_{q}\\}$. Thus the definition implies that every vertex has
at least one coloured vertex in its closed neighbourhood and no colour is
repeated in the closed neighbourhood. Note that the set of coloured vertices
form a dominating set of the graph $G$. Therefore the subset square colouring
is equivalent to square colouring of a dominating set of the graph using $q$
colours.

For a given graph $G$, let $\chi_{ssc}(G)$ be the minimum value of $q$ such
that there exists a $q$-subset square colouring of $G$. We also study the
following algorithmic question. Given a graph $G$, the $q$-Subset Square
Colouring problem is defined as follows,
Input: Graph $G$ and $q\in\mathbb{N}$.
Question: Can $G$ be $q$-subset square coloured$?$
The concept of subset square colouring is previously studied in the context of
a classic problem in Computational Geometry called the Art Gallery problem.
Given a polygon $P$, along with two sets, $M$ and $G$, of points in $P$, the
Art Gallery problem is to find $G^{\prime}\subseteq G$ such that every point
in $M$ is seen by at least one point in $G^{\prime}$. Motivated by
applications in Robotics, Erickson and LaValle [17] introduced the _Chromatic
Art Gallery Problem_. Here, the aim is to find a subset $G^{\prime}\subseteq
G$ such that $G^{\prime}$ can be coloured using $q$ colours and every point
$m\in M$ is seen by at least one point in $G^{\prime}$ and moreover, every
point in $G^{\prime}$ that sees $m$ gets a distinct colour. It is easy to see
that for the case where $M$ and $G$ are the same finite sets, the Chromatic
Art Gallery Problem can be reduced to subset square colouring of a visibility
graph. We believe there exists many other application areas related to Channel
Allocation where the subset square colouring of graphs becomes useful.

Another motivation for studying the $q$-Subset Square Colouring problem is
that many graphs tend to use much smaller number of colours for subset square
colouring when compared to number of colours needed for square colouring. For
example, complete graphs, star graphs, wheel graphs etc. need $O(n)$ colours
for square colouring whereas subset square colouring can be done using one
colour. This will be useful in many applications where the number of colours
corresponds to a resource that needs to be optimized.

We now explore some problems that are related to the $q$-Subset Square
Colouring problem.

Related Problems: The problem of Harmonious colouring was first introduced in
1983 by Hopcroft and Krishnamoorthy [26] and is defined as follows: The
harmonious chromatic number of a graph $G$, denoted by $h(G)$, is the least
number of colours which can be assigned to the vertices of $G$ such that each
vertex has exactly one colour, adjacent vertices have different colours, and
any two edges have different colour pairs. Later, Yue Li Wang et al. [31]
developed the concept of $d-$ Local Harmonious Chromatic problem which
generalized the Harmonious Chromatic problem. The $d$-Local Harmonious (or
just $d$-Harmonious) chromatic problem imposes a restriction that the
different colour-pair requirement is only asked to be satisfied for every edge
within distance $d$ for any vertex. Thus the $1$-Harmonious chromatic problem
is same as the Square colouring problem.

The problem of Efficent Dominating Set [5] for a given graph is also of
interest while we study the subset square colouring problem. An efficent
dominating set is one which is simultaneously an independent and a perfect
dominating set. A perfect dominating set $P$ is one in which, for every vertex
has exactly one neighbour in its open neighbourhood that belongs to $P$,
whereas an independent dominating set $I$ satisfies the condition that set of
vertices in $I$ forms an independent set. Specifically, efficent dominating
set is a special case of subset square colouring with $q=1$.

Another related problem is the Conflict Free Colouring problem [3, 1] which
refers to colouring a dominating set such that every vertex has at least one
distinct colour in its closed neighbourhood.

##  2 A discussion of results

In this section, we give a summary of our results.

We have already mentioned that the Efficient Dominating Set problem is a
special case of $q$-Subset Square Colouring. The Efficient Dominating Set
problem is known to be $NP$-hard [5]. Thus the $q$-Subset Square Colouring
problem is $NP$-hard for $q=1$. We prove that the $q$-Subset Square Colouring
problem with $q=2$ is $NP$-hard even on planar bipartite graphs and the
$q$-Subset Square Colouring problem is $NP$-hard even on bipartite graphs, for
all values of $q$. We also prove that the $q$-Subset Square Colouring problem
is $NP$-hard on chordal graphs.

We consider the parameterized complexity of the $q$-Subset Square Colouring
problem. For any problem, an interesting parameter to be studied is the size
of the solution. For the $q$-Subset Square Colouring problem, this parameter
will be $q$, the number of colours used. However, this turns out to be much
harder than a $W$-hard problem in that it is unlikely to admit an algorithm of
running time of the form $f(q)n^{g(q)}$.

###### Lemma 1

The $q$-Subset Square Colouring problem parameterized by $q$ is
para-$NP$-hard.

The lemma follows from the fact that the $q$-Subset Square Colouring problem
is $NP$-hard even for $q=1$. Moreover, the next result shows that the problem
remains $W$-hard even on graphs of diameter $2$.

###### Theorem 2

The $q$-Subset Square Colouring problem parameterized by $q$ is $W[2]-$hard on
graphs of diameter $2$.

###### Proof 1

For a graph $G$, $\chi_{ssc}(G)$ is bounded by the size of the minimum
dominating set, $D$ of $G$. When the diameter of a graph is two, all vertices
in any $D$ are at distance at most two from each other. Therefore when we
subset square colour the vertices, we can not repeat the colour more than
once. This implies that $\chi_{ssc}(G)$ is equal to the size of the minimum
dominating set. The minimum dominating set problem is known to be $W[2]$-hard
on graphs of diameter $2$ [27]. Thus the result follows.

With respect to Theorem 2, we note that the $q$-Subset Square Colouring
problem is polynomial time solvable on planar graphs with diameter $2$ [28].

Next, we consider several structural parameters. A well studied structural
parameter for graph problems is the treewidth of the graph. Several hard
problems are shown to be $FPT$ when parameterized by treewidth. However, the
$q$-Subset Square Colouring problem can be shown to be $W$-hard when
parameterized by treewidth. Next we consider treewidth and number of colours
as a combined parameter and show that this is $FPT$. This result is proved
using a standard technique in fixed parameter tractable algorithm design
called dynamic programming over treewidth.

Figure 1: Summary of parameterized results.

Next we consider structural parameters which are possibly larger than
treewidth. One such well-studied parameter is the size of the vertex cover of
the graph. We give an $FPT$ algorithm for the $q$-Subset Square Colouring
problem parameterized by the size of the vertex cover and we also show that
the $q$-Subset Square Colouring problem does not admit a polynomial kernel
when parameterized by the size of the vertex cover unless $NP\subseteq
coNP/poly$. The size of vertex cover is usually a large parameter, especially
for dense graphs. Therefore, we study a parameter whose value is small on
dense graphs called the neighbourhood diversity. It is also a parameter whose
value can be computed in polynomial time. We give an $FPT$ algorithm for the
$q$-Subset Square Colouring problem parameterized by neighbourhood diversity
and also we show that it admits a polynomial kernel. Further we consider a
parameter which is a generalization of neighbourhood diversity, called
modular-width and show that the $q$-Subset Square Colouring problem
parameterized by modular-width is $FPT$. We further consider a parameter that
is provably smaller than the size of vertex cover, called the _distance to
cluster graph_ and show that the $q$-Subset Square Colouring problem
parameterized by distance to cluster graph is also $FPT$. We further consider
a parameter called _twin cover_ whose value typically lies between those of
distance to cluster graph and size of vertex cover. Since the $q$-Subset
Square Colouring problem parameterized by distance to cluster graph is $FPT$,
the $q$-Subset Square Colouring problem parameterized by twin cover is also
$FPT$. However, we give an algorithm with a better running time.

For these problems, as our goal is to only show whether or not the problem is
FPT, we do not try to optimize the running times. See Figure 1 for a summary
of the results in parameterized complexity of the $q$-Subset Square Colouring
problem.

Graph Classes |  $\chi_{ssc}$:Upper bound |  $\chi_{ssc}$:Lower bound
---|---|---
Path $P_{n}$ |  $1$ |  $1$
Cycle $C_{3n}$ |  $1$ |  $1$
Cycle $C_{3n+1}$ or $C_{3n+2}$ |  $2$ |  $2$
Complete graph $K_{n}$ |  $1$ |  $1$
Complete bipartite graph $G_{n,m}$ |  $2$ |  $2$
Bipartite permutation graph $G_{n,m}$ |  $4$ |  $3$
Planar graphs with diameter $2$ |  $3$ |  $2$
Cograph $G_{n}$ |  $2$ |  $2$
Threshold graph $G_{n}$ |  $1$ |  $1$
Caterpillar graph $G(n,r_{1},r_{2},\cdots r_{t})$ |  $3$ |  $3$
Tree $T(V,E)$ |  $O(\Delta)$ |  $O(\Delta-1)$
Tree $T(V,E)$ |  $O(n)$ |  $\Omega(\sqrt{n})$
Split graph $T(V,E)$ |  $O(n)$ |  $\Omega(\sqrt{n})$
Table 1: Summary of bounds for $\chi_{ssc}$ for different graph classes.

Next we study bounds on $\chi_{ssc}(G)$ when $G$ belongs to certain graph
classes. It is easy to see that various graph classes (that include many
sparse and dense graph classes) like complete graphs, cluster graphs, star
graphs, wheel graphs, paths, cycles, grid graphs etc. are $q$-subset square
colourable where $q$ is a constant. However, when we consider trees, we show
that there exist trees with $n$ vertices, that requires $O(\sqrt{n})$ colours
to be subset square coloured. As trees form a sub-class of bipartite graphs,
this result extends for the class of bipartite graphs also. However, we show
that a well-defined sub-class of bipartite graphs, called the Bipartite
permutation graphs are $4$-subset square colourable. We further show that the
class of threshold graphs are $1$-subset square colourable. Note that
threshold graphs lie in the intersection of split graphs and cographs. We
observe that, while cographs, like threshold graphs, are subset square
colourable using a constant number of colours, there exist split graphs which
require $O(\sqrt{n})$ colours to be subset square coloured. See Table 1 for a
summary of results.

##  3 NP$-$completeness

In this section, we show that the $q$-Subset Square Colouring problem is NP-
complete, for all values of $q$. Note that the $q$-Subset Square Colouring
problem is NP-hard for $q=1$ and it easy to see that the problem is in NP.
Therefore $q$-Subset Square Colouring problem is $NP$-complete when $q=1$.
Now, we consider $q=2$.

###### Theorem 3

The $q$-Subset Square Colouring problem, where $q=2$ is NP-complete, even on
planar bipartite graphs.

###### Proof 2

We give a reduction from the planar Exact cover by $3$-sets(X3C) problem.
Planar X3C (Exact cover by $3$-sets) :
_Input_ : A finite set $X$ with $|X|=3n$ and a collection $S$ of $3$-element
subsets of $X$ with $|S|=m$.
_Question:_ Does $S$ contain an exact cover for $X$, i.e., a sub collection
$S^{\prime}\subseteq S$ such that every element of $X$ occurs in exactly one
member of $S^{\prime}?$
In Planar X3C problem, we have the added constraint that a bipartite graph $M$
such that $V(M)$ corresponds to $X\cup S$ and $E(G)$ is $\\{(x,s)|x\in X,s\in
S,x\in s\\}$ is planar.
Let $(U,S)$ be an instance of the PlanarX3C problem, where
$U=\\{u_{1},u_{2},..,u_{3n}\\}$ and $\mathcal{S}=\\{S_{1},S_{2},.$
$..,S_{m}\\}$. We construct a planar bipartite graph $G$ as follows: For every
element $u_{i}$, we add a vertex $x_{i}$ in $G$ and connect it with an element
gadget $D_{i}$ in $G$. For $1\leq i\leq 3n$, $D_{i}$ is a tree rooted at a
vertex $d_{i}$, as shown in Figure 3(a). Each of the two child nodes of
$d_{i}$ are connected to three leaves. For every set $S_{j}$, $1\leq j\leq m$,
we add a _set gadget_ $T_{j}$ with a vertex $t_{j}$ attached to two leaves
$v_{j}$ and $v_{j}^{\prime}$. We also add a _palette gadget_ $P$ which has two
vertices $p_{1}$ and $p_{2}$ adjacent to each other and each of them attached
to three vertices of degree one. See Figure 3(b).

Figure 2: Constructed graph $G_{\mathcal{S}}$ from Exact cover by 3-sets
insatnce of $S_{1}=\\{x_{1},x_{2},x_{4}\\}$, $S_{2}=\\{x_{2},x_{4},x_{5}\\}$
and $S_{3}=\\{x_{3},x_{5},x_{6}\\}$.

Figure 3: (a)Element gadget, (b)Palette gadget

Further, for $1\leq i\leq 3n,1\leq j\leq m$, we add an edge between $x_{i}$
and $t_{j}$ in $G$, if $u_{i}\in S_{j}$ in $(U,S)$. We also add the edge
between $v_{j}$ and $p_{1}\in P$, for all $1\leq j\leq m$.

We claim that $(U,S)$ has a planar exact-$3$-cover if and only if $G(V,E)$ has
a subset square colouring using two colours.

Assume $G$ admits a subset square colouring, $\chi$, using two colours. The
vertices $p_{1}$ and $p_{2}$ will be coloured using different colours since
each of them has three neighbours of degree one. Assume, without loss of
generality, that $p_{1}$ is coloured green and $p_{2}$ is coloured red.
Similarly, in every element gadget, the two child nodes of $d_{i}$ are
coloured using different colours. Hence the vertices $d_{i}$ and $x_{i}$
cannot be coloured. Therefore $x_{i}$ need to be dominated by a neighbouring
vertex in one of the set gadgets. Moreover, for $1\leq j\leq m$, since $p_{1}$
is coloured green, $t_{j}$ which is at distance two from $p_{1}$, if coloured,
needs to be coloured red. Hence, for every vertex $x_{i}$, there exists a
unique $t_{j}$ which is coloured red and is adjacent to $x_{i}$. Now it is not
difficult to see that $\\{S_{j}|t_{j}$ is coloured red in $\chi\\}$ is a
planar exact-$3$-cover for $(U,S)$. See Figure 3.

For the other direction, assume $(U,S)$ has a planar exact-$3$-cover
$\mathcal{S}^{\prime}$. Now we give a subset square colouring of $G$ using two
colours. Colour the vertices $p_{1}$ and $p_{2}$ using green and red colours
respectively. For $1\leq i\leq 3n$, colour the two child nodes of $d_{i}$
using different colours, in the element gadget $D_{i}$. For $1\leq j\leq m$,
if $S_{j}\in\mathcal{S}^{\prime}$ then colour $t_{j}$ red, otherwise colour
the vertex $v_{j^{\prime}}$ using any colour. This gives a subset square
colouring of $G$.

Now, the result follows from the NP-hardness of the planar X3C problem [21].

###### Theorem 4

The $q$-Subset Square Colouring problem, where $q>2$ is NP-complete, even on
bipartite graphs.

###### Proof 3

The proof is very similar to that of Theorem 5. We give a reduction from the
X3C problem. Similar to the previous proof, we construct a bipartite graph $G$
corresponding to an instance $(U,S)$ of the X3C problem. Here the element and
palette gadgets $D$ and $P$ are slightly different.

For every element $u_{i}$, we add a vertex $x_{i}$ in $G$ and connect it with
an element gadget, $D_{i}$, such that $D_{i}$ is a tree rooted at a vertex
$d_{i}$ and each of the $q$ child nodes of $d_{i}$ is connected to $q+1$
leaves. For every set $S_{j}$, $1\leq j\leq m$, we add a _set gadget_ ,
$T_{j}$, in the same way as given in the proof of Theorem 5. We further add a
_palette gadget_ $P$ which has a path with $q$ vertices
$p_{1},p_{2},\cdots,p_{q}$ and each vertex in the path is attached to $q+1$
vertices of degree one.

Furthermore, for $1\leq i\leq 3n,1\leq j\leq m$, we add the edge between
$x_{i}$ and $t_{j}$ in $G$, if $u_{i}\in S_{j}$ in $(U,S)$. We also add edges
between $v_{j}$ and the vertices $p_{1},p_{2},\cdots,p_{q-1}\in P$, for all
$1\leq j\leq m$. See Figure 4.

By the same arguments as given in the proof of Theorem 5, we can now see that
$G$ has a subset square colouring using $q$ colours if and only if $(U,S)$ has
an exact cover by 3-sets.

Figure 4: Constructed graph $G_{\mathcal{S}}$ from Exact cover by 3-sets
insatnce of $S_{1}=\\{x_{1},x_{2},x_{4}\\}$, $S_{2}=\\{x_{2},x_{4},x_{6}\\}$
and $S_{3}=\\{x_{3},x_{5},x_{6}\\}$.

Now, we show that the $q$-Subset Square Colouring problem is NP-Complete on
chordal graphs for all values of $q$.

###### Theorem 5

The $q$-Subset Square Colouring problem is NP-complete on chordal graphs for
all values of $q$.

###### Proof 4

We give a reduction from the Vertex Cover problem. Let $(G,k)$ be an instance
of the Vertex Cover problem, where $|V|=n$ and $|E|=m$. We construct a chordal
graph $G^{\prime}=(V^{\prime},E^{\prime})$ as follows. For every vertex
$v_{i}\in V(G)$, we introduce a vertex $v^{\prime}_{i}$ in $G^{\prime}$ and
similarly for every edge $e_{j}\in E(G)$, we introduce a vertex
$e^{\prime}_{j}$ in $G^{\prime}$. For every vertex $e^{\prime}_{j}$ that
corresponds to en edge $e_{j}=(i,h)\in E$, we add edges
$(v^{\prime}_{i},e^{\prime}_{j})$ and $(v^{\prime}_{h},e^{\prime}_{j})$. We
further connect every pair of vertices $v^{\prime}_{i}$ in $G^{\prime}$, thus
forming a clique $C$ of size $|V(G)|$.

Further, for every vertex $e^{\prime}_{j}$ where $1\leq j\leq|E(G)|$, we add a
subtree $T_{j}$. The subtree $T_{j}$ contains a root node $r_{j}$ with $k$
child nodes and each of these child node is adjacent to $k+1$ leaf nodes. We
connect the subtree $T_{j}$ with $e^{\prime}_{j}$ by adding an edge between
$r_{j}$ and $e^{\prime}_{j}$.

Apart from the subgraphs that induce trees, the constructed graph $G^{\prime}$
contains a clique and a set of vertices $e^{\prime}_{j}$ that are adjacent to
vertices of clique. Therefore every induced cycle in $G^{\prime}$ has exactly
three vertices. Hence, it is easy to see that $G^{\prime}$ is a chordal graph,
and it can be constructed in polynomial time.

###### Observation 6

In every $T_{j}$, any $k$\- subset square colouring colours the $k$ child
nodes of $r_{j}$ using $k$ different colours.

The result follows from the fact that the root node $r_{j}$ is adjacent to $k$
child nodes and each of these child node is adjacent with $k+1$ leaf nodes.
Therefore to dominate these leaf nodes, we need to colour the $k$ child nodes
of $r_{j}$ using $k$ different colours.

Figure 5: Chordal graph $G^{\prime}(V^{\prime},E^{\prime})$ is constructed
from the graph $G(V,E)$.

###### Lemma 7

The graph $G$ has a vertex cover of size $k$ if and only if $G^{\prime}$
admits a $k$-subset square colouring.

###### Proof 5

Assume $G^{\prime}$ has a $k$\- subset square colouring. From Observation 6,
we can see that none of the root nodes in the subtrees and none of the
vertices $e^{\prime}_{j}$ can be coloured, in a $k$\- subset square colouring
of $G^{\prime}$. Therefore to dominate the vertex $e^{\prime}_{j}$, we need to
colour either of the vertices in the clique $C$, that it is adjacent to. We
can not repeat any colour in $C$ and hence at most $k$ vertices in $C$ are
coloured. It is easy to see that the set of coloured vertices corresponds to a
vertex cover in $G$. The other direction is similar and easy to see. See
Figure 5.

Now, the result follows from the NP-completeness of the Vertex Cover problem.

##  4 Parameterized Complexity

In this section, we study the parameterized complexity of the $q$-Subset
Square Colouring problem.

A parameterized problem is a language $L\subseteq\Sigma^{*}\times\mathbb{N}$,
where $\Sigma$ is a fixed, finite alphabet. For an instance
$(x,k)\in\Sigma^{*}\times\mathbb{N}$, $k$ is called the parameter. The
complexity class FPT contains all fixed parameter tractable problems that have
an algorithm, a computable function $f:\mathbb{N}\rightarrow\mathbb{N}$, and a
constant $c$ such that, given $(x,k)\in\Sigma^{*}\times\mathbb{N}$, the
algorithm correctly decides whether $(x,k)\in L$ in time bounded by
$f(k)\cdot|(x,k)|^{c}$ [16]. Theory of intractability of parameterized
problems orders the problems into a hierarchy called the $W$-hierarchy based
on its complexity. It is organized as FPT $\subseteq W[1]\subseteq
W[2]\cdots$. Under standard complexity theoretical assumptions, a problem
which is $W[i]$-hard does not admit FPT algorithms, where $i>0$. For detailed
reading of parameterized complexity, refer [15].

As mentioned in the introduction, the Efficient Dominating Set problem is a
special case of the subset square colouring, when $q=1$. However, the problem
of finding an Efficient Dominating Set is NP-hard [5]. Hence, the problem of
the $q$-Subset Square Colouring is also NP-hard. Therefore, we explore the
possibility of algorithms that are fixed parameter tractable to find subset
square colouring of a graph. But with respect to the standard parameter $q$,
the problem is para-NP-hard since it is NP-hard even for $q=1$ (see Lemma 1).
Therefore we investigate the problem of subset square colouring parameterized
by structural parameters.

###  4.1 Parameterized by treewidth

We first consider one of the common and well studied structural parameter of
the graph called treewidth. We begin by defining treewidth.

Tree Decomposition: [15] A tree decomposition of a graph $G$ is a tree $T$ in
which each vertex $i\in T$ has an assigned set of vertices $X_{i}\subseteq V$,
called the bag, such that $\displaystyle\bigcup_{i\in T}X_{i}=V$, with some
properties:

  * 1.

If $u\in X_{i}$ and $u\in X_{k}$, then $u\in X_{j}$ for all $j$ on the path
from $i$ to $k$ in $T$.

  * 2.

For any edge $e(u,v)\in E(G)$, there exists an $i\in T$ such that $u,v\in
X_{i}$.

The width of a tree decomposition $T$ is the size of the largest bag of $T$
minus one, and the treewidth of a graph $G$, denoted by $\tau(G)$, is the
minimum width over all possible tree decompositions of $G$.

Treewidth is a measure of how close a graph is to a tree-like structure.

###### Theorem 8

The $q$-Subset Square Colouring problem parameterized by treewidth is
$W[1]$-hard.

We give a sketch of the proof. A problem which is closely related to the
subset square colouring is the problem of L(1,1)-Labeling. Theorem $5$ of [18]
proves that the Square Colouring problem is $W[1]$-hard parameterized by
treewidth. They give a parameterized reduction that convert any instance
$(G,r)$ of Equitable colouring problem parameterized by number of colours $r$
to an instance $(H,\tau)$ of Square Colouring problem parameterized by
treewidth $\tau$ such that $\tau$ is bounded by a function of $r$, and the
graph $G$ has an equitable colouring by $r$ colours if and only if $H$ has a
square colouring using $r$ colours.

###### Definition 2

Equitable Colouring parameterized by $r$:
_Input_ : A graph $G$ and a positive integer $r$.
_Question:_ Is there a vertex colouring $c$ of $G$ using at most $r$ colours
such that the sizes of any two colour classes differ by at most one $?$

We modify the reduction given in [18] as follows to get an instance of the
$q$-Subset Square Colouring problem. To the reduced graph $H$, we add $q+1$
number of degree-$1$ vertices to each $v\in V(H)$, to obtain the graph
$H^{\prime}$. This forces all the vertices in $V(H)$ to be coloured in any
$q$-subset square colouring of $H^{\prime}$ since otherwise, if $v\in V(H)$ is
not coloured, we have to colour each of the $q+1$ neighbours of $v$ that we
introduced in graph $H^{\prime}$, which clearly overshoots the given budget of
$q$ colours. Further, note that this modification does not alter the treewidth
of $H$ and treewidth is bounded by a function of $r$. Now, we can see that the
graph $G$ has an equitable colouring by $r$ colours if and only if
$H^{\prime}$ has a subset square colouring. Thus, we give a parameterized
reduction from the Equitable Colouring problem parameterized by $r$ to the
$q$-Subset Square Colouring problem parameterized by $\tau$.

###  4.2 Parameterized by treewidth and number of colours

We now consider the $q$-Subset Square Colouring problem parameterized by
treewidth and number of colours and give an $FPT$ algorithm. We use a standard
technique called dynamic programming over treewidth, which gives a
constructive proof for the fixed parameter tractability. We use a modified
tree decomposition called the nice tree decomposition.

Nice Tree Decomposition:[15]A tree decomposition with a distinguished root is
called a nice tree decomposition if:

\- All leaf nodes and the root node have empty bags, i.e., $X_{l}=X_{r}=\phi$,
where $r$ is the root node and $l$ is a leaf node.

\- Every other node in the tree decomposition falls in one of the three
categories:

Introduce node: An introduce vertex node $t$ has exactly one child
$t^{\prime}$ such that $X_{t}=X_{t^{\prime}}\cup\\{v\\}$ for some $v\not\in
X_{t^{\prime}}$.

Forget Node: A forget node $t$ has exactly one child $t^{\prime}$ such that
$X_{t}=X_{t^{\prime}}\setminus\\{w\\}$ for some $w\in X_{t^{\prime}}$.

Join Node: A join node $t$ has exactly two children $t_{1}$ and $t_{2}$, such
that $X_{t}=X_{t_{1}}=X_{t_{2}}$.

Introduce edge node: An introduce edge node is labeled with an edge $uv\in
E(G)$ such that $u,v\in X_{t}$ and has exactly one child node $t^{\prime}$
such that $X_{t}=X_{t^{\prime}}$.

Note that we assume every edge is introduced exactly once. If a join node
contains both $u$ and $v$, and the edge $uv$ exists in $E(G)$, we can note
that edge $uv$ will be introduced in the subtree above the join node.

Nice tree decomposition enables us to add edges and vertices one by one and
perform operations accordingly. This variant of tree decomposition still has
$O(\tau\cdot n)$ nodes, where $\tau$ is the treewidth of the graph $G$.

The following result is known.

###### Proposition 9

Given a graph $G$, in time $2^{O(\tau)}n$, we can compute a nice tree
decomposition $(T,{\cal X})$ of $G$ with $|V(T)|\in|V(G)|^{O(1)}$ and of width
at most $5\tau$, where $\tau$ is the treewidth of $G$ [7].

With each node $t$ of the tree decomposition we associate a subgraph $G_{t}$
of $G$ defined as: $G_{t}=\left(V_{t},E_{t}=\\{e:e\text{ is introduced in the
subtree rooted at t\\}}\right)$. Here, $V_{t}$ is the union of all bags
present in the subtree rooted at $t$.

###### Theorem 10

The $q$-Subset Square Colouring is FPT when parameterized by the treewidth
$\tau$ of the input graph and the number of colours $q$.

###### Proof 6

We give an algorithm based on dynamic programming over nice tree decomposition
$(T,{\cal X})$ of $G$, computed in time $2^{O(\tau)}n$, using Proposition 9,
of width at most $5\tau$, where $\tau$ is the treewidth of $G$. We define
subproblems on $t\in V(T)$ for the graph $G_{t}$. We consider a partitioning
of bag $X_{t}$ by a mapping $f:X_{t}\rightarrow\\{B,W,R\\}$. For simplicity,
we refer to the vertices in each partition respectively as black, white and
grey. Each vertex is also assigned another colour by a function $c$ :
$X_{t}\rightarrow\\{c_{0},c_{1},...,c_{q}\\}$ and a $q$-length tuple, by a
function $\Gamma$: $X_{t}\rightarrow\\{0,1,\hat{1}\\}^{q}$. Roughly speaking,
these functions will determine how the “partial” square colouring looks like,
when restricted to $G_{t}$ and vertices of $X_{t}$. Here, $c(v)$ denotes the
colour assigned to $v$ and $c(v)=c_{0}$ denotes that $v$ is not coloured.
Also, $\Gamma(v)[i]$ indicates whether $v$ has (either in the current graph,
or in the “future”) a vertex in its closed neighbourhood that has colour
$c_{i}$. Also, $\Gamma(v)[i]=1$ denotes that vertex $v$ has a vertex in its
closed neighbourhood of colour $c_{i}$ in $G_{t}$, $\Gamma(v)[i]=\hat{1}$
denotes that vertex $v$ has a vertex in its closed neighbourhood of colour
$c_{i}$, that is not present in $G_{t}$, but will appear in the “future”, and
$\Gamma(v)[i]=0$ denotes the absence of colour $c_{i}$ in the closed
neighbourhood of $v$. We slightly abuse the notation and use
$\Gamma(v)[c_{i}]$ and $\Gamma(v)[i]$ interchangeably. In the following we
give a detailed insight into the functions $f$, $c$ and $\Gamma$.
Black, represented by $B$. Every black vertex $v$ is given a colour $c(v)\neq
c_{0}$ in a subset square colouring.
Grey, represented by $R$. A grey vertex $v$ is not coloured, not dominated,
i.e. $c(v)=c_{0}$ and for each $i\in[q]$, it has
$\Gamma(v)[i]\in\\{0,\hat{1}\\}$.
White, represented by $W$. A vertex $v$ that is neither black nor grey is a
white vertex. Note that for a white vertex $v$, $c(v)=c_{0}$ and there is
$i\in[q]$, such that $\Gamma(v)[i]=1$.

A tuple $(t,c,\Gamma,f)$ is _valid_ if the following conditions hold for every
vertex $v\in X_{t}$:

  1. 1.

$f(v)=B\implies c(v)\neq c_{0}$ and $\Gamma(v)[c(v)]=1$,

  2. 2.

$f(v)=R\implies c(v)=c_{0}$ and $\Gamma(v)[i]\in\\{0,\hat{1}\\}$, $\forall
i\in\\{1...q\\}$, and

  3. 3.

$f(v)=W\implies c(v)=c_{0}$ and $\Gamma(v)[i]=1$ for some $i\in\\{1...q\\}$.

For a node $t\in V(T)$, for each valid tuple $(t,c,\Gamma,f)$, we have a table
entry denoted by $D[t,c,\Gamma,f]$. We have $D[t,c,\Gamma,f]=true$ if and only
if there is ${\sf col}:V_{t}\rightarrow\\{c_{0},c_{1},\ldots,c_{q}\\}$ (where
$c_{0}$ denotes no colour assignment), such that:

  1. 1.

${\sf col}|_{X_{t}}=c$,

  2. 2.

for each $v\in X_{t}$ and $i\in\\{1,2,\dots q\\}$ with $\Gamma(v)[i]=1$, there
is exactly one vertex $u\in N_{G_{t}}[v]$, such that $\sf col(u)=c_{i}$,

  3. 3.

for each $v\in X_{t}$ and $i\in[q]$ with $\Gamma(v)[i]\in\\{0,\hat{1}\\}$,
there is no vertex $u\in N_{G_{t}}[v]$, such that $\sf col(u)=c_{i}$, and

  4. 4.

for each $v\in V_{t}\setminus X_{t}$, there is at least one vertex $u\in
N_{G_{t}}[v]$, such that $\sf col(u)\neq c_{0}$, and for all such vertices
$u$, every other $u^{\prime}\in N_{G_{t}}[v]$ have ${\sf
col}(u^{\prime})\neq{\sf col}(u)$.

In the above, such a colouring $\sf col$ is called a $(t,c,\Gamma,f)$-_good_
colouring. (At any point of time wherever we query an invalid tuple, then its
value is $false$ by default.) Note that
$D[r,\emptyset,\emptyset,\emptyset]=true$, where $r$ is the root of the tree
decomposition, if and only if $G$ admits a subset square colouring using (at
most) $q$ colours.
We define $f_{v\rightarrow\gamma}$ where $\gamma\in\\{B,W,R\\}$, as the
function where $f_{v\rightarrow\gamma}(x)=f(x)$, if $x\neq v$, and
$f_{v\rightarrow\gamma}(x)=\gamma$, otherwise. Similarly, we define the
functions $c_{v\rightarrow c_{i}}$ and $\Gamma_{v[i]\rightarrow\alpha}$ where
$\alpha\in\\{0,\hat{1},1\\}$ . We now proceed to define the recursive formulas
for the values of $D$.

Leaf node. For a leaf node $t$, we have $X_{t}=\emptyset$. Hence, the only
entry is $D[t,\emptyset,\emptyset,\emptyset]$. Moreover, by definition, we
have $D[t,\emptyset,\emptyset,\emptyset]=true$.

Introduce vertex node. Let $t$ be the introduce vertex node with a child
$t^{\prime}$ such that $X_{t}=X_{t^{\prime}}\cup\\{v\\}$ for some $v\not\in
X_{t^{\prime}}$. Since the vertex $v$ is isolated in $G_{t}$, the following
recurrence follows.

$\displaystyle D[t,c,\Gamma,f]=$
$\displaystyle\begin{cases}D[t^{\prime},c_{|X^{\prime}},\Gamma_{|X^{\prime}},f_{|X^{\prime}}]\text{
if }&f(v)=B\text{ and }\Gamma(v)[c_{i}]\in\\{0,\hat{1}\\}\text{
},\forall\text{ }c_{i}\neq c(v)\\\
D[t^{\prime},c_{|X^{\prime}},\Gamma_{|X^{\prime}},f_{|X^{\prime}}]\text{ if
}&f(v)=R\\\ \text{False }&\text{otherwise}\end{cases}$

Introduce edge node. Let $t$ be an introduce edge node labeled with an edge
$u^{*}v^{*}$ and let $t^{\prime}$ be the child of it. Thus $G_{t^{\prime}}$
does not have the edge $u^{*}v^{*}$ but $G_{t}$ has. Consider distinct
$u,v\in\\{u^{*},v^{*}\\}$.

  1. 1.

If $f(u)=B$, $f(v)=W$ and $\Gamma(v)[c(u)]=1$. We set
$D[t,c,\Gamma,f]=D[t^{\prime},c,$ $\Gamma_{v[c(u)]\rightarrow\hat{1}}$,
$f_{v\rightarrow R}]\vee D[t^{\prime},c,\Gamma_{v[c(u)]\rightarrow\hat{1}}$,
$f_{v\rightarrow W}]$ (if any of the entries are invalid, then it is $false$).

  2. 2.

If $f(u)=f(v)=B$ and $\Gamma(v[c(u)])=\Gamma(u[c(v)])=1$, set
$D[t,c,\Gamma,f]=D[t^{\prime},c,\Gamma_{v[c(u)]\rightarrow\hat{1},u[c(v)]\rightarrow\hat{1}},f]$.

  3. 3.

If $\\{f(u),f(v)\\}\cap\\{B\\}=\emptyset$, then
$D[t,c,\Gamma,f]=D[t^{\prime},c,\Gamma,f]$.

  4. 4.

If none of the above conditions hold then $D[t,c,\Gamma,f]=false$.

###### Lemma 11

Recurrence for introduce edge node is correct.

###### Proof 7

Note that all the vertices except $u$ and $v$ in $X_{t}$ are unaffected by
introduction of edge $u^{*}v^{*}$. Also if neither $u$ nor $v$ are black, then
the edge $uv$ cannot affect the domination of any vertex. Therefore the value
of $D$ for that tuple is same as that in the child node.

Consider the case where $f(u)=B$ and $f(v)=W$ and $\Gamma(v)[c(u)]=1$. We show
that $D[t,c,\Gamma,f]=true$ when at least one of
$D[t^{\prime},c,\Gamma_{v[c(u)]\rightarrow\hat{1}},f_{v\rightarrow R}]$ and
$D[t^{\prime},c,\Gamma_{v[c(u)]\rightarrow\hat{1}},f]$ is $true$. Let
$D[t^{\prime},c,\Gamma_{v[c(u)]\rightarrow\hat{1}},f_{v\rightarrow R}]=true$.
Let $\sf col:V_{t\prime}\rightarrow\\{c_{0},\dots,c_{q}\\}$ be a
$(t^{\prime},c,\Gamma_{v[c(u)]\rightarrow\hat{1}},f_{v\rightarrow R})$-good
colouring in $G_{t^{\prime}}$. Note that $\sf col(v)=c_{0}$ and there is no
vertex $v^{\prime}\in N_{G_{t^{\prime}}}[v]$ such that $\sf
col(v^{\prime})=c(u)$. Therefore, $\sf col$ is also a $(t,c,\Gamma,f)$-good
colouring since $u$ is the unique vertex in $N_{G_{t}}[v]$ with $\sf
col(u)=c(u)$. Hence $D[t,c,\Gamma,f]=true$. Similarly, we can prove that when
$D[t^{\prime},c,\Gamma_{v[c(u)]\rightarrow\hat{1}},f]=true$, any
$(t^{\prime},c,\Gamma_{v[c(u)]\rightarrow\hat{1}},f)$-good colouring is also a
$(t,c,\Gamma,f)$\- colouring. In the reverse direction, assume
$D[t,c,\Gamma,f]=true$ and let $\sf
col:V_{t}\rightarrow\\{c_{0},\dots,c_{q}\\}$ be a $(t,c,\Gamma,f)$ \- good
colouring. Therefore, $u$ is the unique vertex in $N_{G_{t}}[v]$ such that
$\sf col(u)=c(u)$. If there exists a $c_{i}\neq c(u)$ such that $v$ has a
neighbour $v^{\prime}$ in $N_{G_{t}}[v]$ with $\sf col(v^{\prime})=c_{i}$,
then $\sf col$ is a
$(t^{\prime},c,\Gamma_{v[c(u)]\rightarrow\hat{1}},f)$-colouring, otherwise
$\sf col$ is a
$(t^{\prime},c,\Gamma_{v[c(u)]\rightarrow\hat{1}},f_{v\rightarrow
R})$-colouring. We can prove the correctness for other cases by similar
arguments.

Forget node. Let $t$ be a forget node with child $t^{\prime}$ such that
$X_{t}=X_{t^{\prime}}\setminus\\{v\\}$ for some $v\in X_{t^{\prime}}$. Since
the vertex $v$ does not appear again in any bag of a node above $t$, $v$ must
be either black or white (otherwise, we set the entry to $false$).

$\displaystyle D[t,c,\Gamma,f]=\bigvee_{\begin{subarray}{c}1\leq i\leq q\\\
\alpha\in\\{0,1\\}^{q}\end{subarray}}\left(D[t^{\prime},c_{v\rightarrow
c_{0}},\Gamma_{v\rightarrow\alpha},f_{v\rightarrow W}]\vee
D[t^{\prime},c_{v\rightarrow
c_{i}},\Gamma_{v\rightarrow\alpha},f_{v\rightarrow B}]\right)$

Join node. Let us denote the the join node by $t$. Let $t_{1}$ and $t_{2}$ be
the children of $t$. We know that $X_{t}=X_{t_{1}}=X_{t_{2}}$ and $X_{t}$
induces an independent set in the graphs $G_{t}$, $G_{t_{1}}$ and $G_{t_{2}}$.
We say that the pair of tuples $[t_{1},f_{1},c_{1},\Gamma_{1}]$ and
$[t_{2},f_{2},c_{2},\Gamma_{2}]$ are $[t,f,c,\Gamma]$-consistent if for every
$v\in X_{t}$ the following conditions hold.

  * 1.

If $f(v)=B$ then $(f_{1}(v),f_{2}(v))=(B,B)$ and $c_{1}(v)=c_{2}(v)=c(v)$.

  * 2.

If $f(v)=W$ then $(f_{1}(v),f_{2}(v))\in\\{(W,R),(R,W),(W,W)\\}$.

  * 3.

If $f(v)=R$ then $(f_{1}(v),f_{2}(v))=(R,R)$.

  * 4.

If $\Gamma(v)[i]=0$ then $(\Gamma_{1}(v)[i],\Gamma_{2}(v)[i])\in\\{(0,0)\\}$
for $1\leq i\leq q$.

  * 5.

If $\Gamma(v)[i]=1$ then
$(\Gamma_{1}(v)[i],\Gamma_{2}(v)[i])\in\\{(1,\hat{1}),(\hat{1},1)$} for $1\leq
i\leq q$.

  * 6.

If $\Gamma(v)[i]=\hat{1}$ then
$(\Gamma_{1}(v)[i],\Gamma_{2}(v)[i])\in\\{(\hat{1},\hat{1})\\}$ for $1\leq
i\leq q$.

It is easy to see that a vertex $v$ belongs to Black partition in $X_{t}$ if
it is Black in $X_{t_{1}}$ and $X_{t_{2}}$ and the colour $c(v)$ that is
assigned to $v$ is same in these bags. Similarly, we can understand for a
vertex in Grey partition. If vertex $v$ belongs to White partition, it implies
that it is dominated in exactly one of the bags $X_{t_{1}}$ and $X_{t_{2}}$ or
both. However if $v$ is dominated in both the bags, then the colour that
dominates it is different which is taken care by $\Gamma(v)[i]$. The value of
$\Gamma(v)[i]$ is set to 1 for different values of the $q$-length tuple.
Therefore, for a vertex to belong to White partition requires one of the three
combinations: $\\{(W,R),(R,W),(W,W)\\}$. Now consider the values that
$\Gamma(v)[i]$ can take in $X_{t}$. If colour $i$ is not present in $N[v]$ in
any of the child nodes $t_{1}$ and $t_{2}$, then it will naturally not be
present in $N[v]$ in $G_{t}$, implying $\Gamma(v)[i]=0$. However,
$\Gamma(v)[i]=1$ indicates the presence of a vertex with colour $i$ in $N[v]$
in $G_{t}$. We further note that colour $i$ appears in exactly one of the
child nodes $X_{t_{1}}$ or $X_{t_{2}}$ but not both because presence of colour
$i$ in both child nodes implies the presence of two vertices with colour $i$
in $N[v]$ in $G_{t}$. This follows from the observation that $X_{t}$ induces
an independent set in $G_{t}$, by the property of nice tree decomposition. The
next possibility of $\Gamma(v)[i]$ is $\hat{1}$. For this to be true, the
colour $i$ should not be present in $G_{t}$ seen so far but will appear in the
tree decomposition eventually.

We set
$D[t,c,\Gamma,f]=\bigvee_{\begin{subarray}{c}(f_{1},f_{2})\end{subarray}}\left({D[t_{1},c_{1},\Gamma_{1},f_{1}]\wedge
D[t_{2},c_{2},\Gamma_{2},f_{2}]}\right)$, where $[t_{1},f_{1}$,
$c_{1},\Gamma_{1}]$ and
$[t_{2},f_{2},c_{2},\Gamma_{2}]$ is $[t,f,c,\Gamma]$-consistent.

We have described the recursive formulas for the values of $D[\cdot]$. Note
that we can compute each entry in time bounded by $2^{O(q\tau)}\cdot
q^{O(\tau)}n^{O(1)}$. Moreover, the number of (valid) entries for a node $t\in
V(T)$ is bounded by $2^{O(q\tau)}\cdot q^{O(\tau)}n^{O(1)}$, and $V(T)\in
n^{O(1)}$. Thus we can obtain that the overall running time of the algorithm
is bounded by $2^{O(q\tau)}n^{O(1)}$.

###  4.3 Parameterized by the size of vertex cover

In this section, we prove that the $q$-Subset Square Colouring parameterized
by the size of vertex cover is FPT. Let $X$ be a vertex cover of $G$, $|X|=k$.
First we prove the following result.

###### Lemma 12

The number of colours required to subset square colour the vertices of graph
$G$ is at most the size of vertex cover of $G$.

###### Proof 8

We know that every edge $e\in E(G)$ has at least one of its end vertices in
vertex cover of $G$. Consider a graph $G$ with a vertex cover $X$ of size $k$.
Firstly, assign one of the $k$ colours to all isolated vertices, if they
exist. Next colour every vertex in $X$ using $k$ different colours. Since we
colour each vertex of $X$, every vertex $v\in V$ is either coloured or has at
least one coloured vertex in its open neighbourhood. Moreover, each vertex in
$X$ is coloured using a different colour which avoids overlapping of colours.
The result follows.

Since both the treewidth and number of colours required to subset square
colour is bounded by $|X|$, the following theorem follows from Theorem 10.

###### Theorem 13

The $q$-Subset Square Colouring parameterized by the size of vertex cover is
FPT.

Now, we discuss the existence of polynomial kernels for $q$-Subset Square
Colouring problem parameterized by the size of vertex cover. A polynomial
kernel exists for the $q$-Subset Square Colouring problem, when $q=1$ by a
result given in [4]. We prove that the $q$-Subset Square Colouring problem
parameterized by the size of vertex cover does not have a polynomial kernel
unless $NP\subseteq coNP/poly$ for $q\geq 2$. Here we use the or-cross-
composition technique for proving kernelization lower bounds. In order to
simplify the proof, we first prove the result for $q=2$, and then we extend
the result for $q\geq 3$.

###### Definition 3

OR-Cross-composition [15]. Let $L\subseteq\Sigma^{*}$ be a language and
$Q\subseteq\Sigma^{*}\times N$ be a parameterized language. We say that $L$
cross-composes into $Q$ if there exists a polynomial equivalence relation R
and an algorithm $\mathcal{A}$, called the cross-composition, satisfying the
following conditions. The algorithm $\mathcal{A}$ takes as input a sequence of
strings $x_{1},x_{2},\cdots,x_{t}\in\Sigma^{*}$ that are equivalent with
respect to R, runs in time polynomial in $\sum_{i=1}^{t}|x_{i}|$, outputs one
instance $(y,k)\in\Sigma^{*}\times N$ such that:

  * 1.

$k\leq p(\max_{i=1}^{t}|x_{i}|+\log t)$ for some polynomial $p(.)$, and

  * 2.

$(y,k)\in Q$ if and only if there exist at least one index $i$ such that
$x_{i}\in L$.

We use the technique OR-cross-composition given by Bodlaender et al.[8].

###### Definition 4

If an NP-hard problem $L$, OR-cross-composes into a parameterized problem $Q$,
then Q does not admit a polynomial kernel unless $NP\subseteq coNP/poly$ and
the polynomial hierarchy collapses [8].

####  4.3.1 Kernalization: $2$-Subset square colouring problem parameterized
by the size of vertex cover

We show that $2$-Subset square colouring problem parameterized by the size of
vertex cover does not admit a polynomial kernel unless $NP\subseteq coNP/poly$
by giving an OR-cross-composition from the NP-hard problem Clique. This
framework is similar to the framework used in [10, 3].

In this reduction we consider $t$ instances $X_{1},X_{2},\cdots,X_{t}$ of the
Clique. The instances are said to be equivalent if the number of vertices of
each $X_{i}$ is $n$ and asks for a $k$ sized clique. Let
$\\{v_{l1},v_{l2},\cdots,v_{ln}\\}$ be the set of vertices in an arbitrary
instance $X_{l}$, where $1\leq l\leq t$. In this section, we assume that
$c_{1}=$ red and $c_{2}=$ blue.

We define a _special vertex_ before creating an instance $G$ for $2$-Subset
square colouring.

Special vertex : If $N(v)$ contains three single-degree vertices, then the
vertex $v$ is a special vertex. We denote the special vertex by two circles
with the same centre and different radius (Figure 6).

Figure 6: Special vertex coloured with red and blue respectively.

###### Observation 14

For any $2$-subset square colouring $C$ of $G$, if a vertex $v$ in $G$ is a
special vertex, then $C(v)\neq c_{0}$.

We follow some steps to create an instance $G$ of the $2$-subset square
colouring. We add two special vertices $R$ and $B$ and we add an edge between
$R$ and $B$. This ensures that the vertices $R$ and $B$ receive distinct
colours in any $2$-subset square colouring. Without loss of generality, assume
that $R$ receives the colour red and $B$ receives the colour blue.

Now we add a set of vertices $\\{p_{i,j}|i\in[k],j\in[n]\\}$, called grid
vertices of $G$. These vertices are intuitively used to select the vertices
that correspond to a clique in one of the input instances.

In order to complete the construction, we need to create the following
gadgets. We connect those gadgets to the grid vertices and also with the
special vertices $R$ and $B$.

For every $i\in[k]$, we add a path gadget $\mathcal{P}1_{i}$ with three
vertices $r^{\prime}_{i},r_{i},$ and $r^{\prime\prime}_{i}$. In every
$\mathcal{P}1_{i}$, there exist edges $(r^{\prime}_{i},r_{i})$ and
$(r_{i},r^{\prime\prime}_{i})$, where $r_{i}$ is a special vertex. These
vertices form a path in the path gadget. See Figure 9. In addition to that,
connect $\mathcal{P}1_{i}$ to the vertex $R$, by adding an edge between
$r^{\prime}_{i}$ and $R$. Moreover $\mathcal{P}1_{i}$ connects to grid
vertices through $r_{i}$ by adding edges $(r_{i},p_{i,j})$, for all $j\in[n]$.

For every $j\in[n]$, we use a similar path gadget, $\mathcal{P}2_{j}$ with
three vertices $w_{j}$, $w^{\prime}_{j}$ and $w^{\prime\prime}_{j}$. In every
$\mathcal{P}2_{j}$, there exist edges $(w_{j},w^{\prime}_{j})$ and
$(w^{\prime}_{j},w^{\prime\prime}_{j})$, where $w^{\prime}_{j}$ is a special
vertex. See Figure 9. Moreover, we add a vertex $w$ and connect
$\mathcal{P}2_{j}$ to the vertex $R$, by adding edges $(w_{j},w)$ and $(w,R)$.
Also, connect the vertices $w^{\prime\prime}_{j}$ and $R$. In addition to
that, we connect $\mathcal{P}2_{j}$ with grid vertices by adding edges
$(w_{j},p_{i,j})$, for all $i\in[k]$.

Figure 7: Path gadget $\mathcal{P}1_{i}$

Figure 8: Path gadget $\mathcal{P}2_{j}$

Figure 9: Hanging gadget

###### Observation 15

For any $2$-subset square colouring $C$ of $G$, for all $i\in[k],j\in[n]$,
$C(r_{i})=$ blue and $C(w^{\prime}_{j})=$ blue and all other vertices in path
gadgets $\mathcal{P}1_{i}$ and $\mathcal{P}2_{j}$ are dominated by $r_{i}$ and
$w^{\prime}_{j}$, respectively.

We continue the construction of $G$ by creating a connector gadget
$S^{i,i^{\prime}}_{j,j^{\prime}}$, for every $i,i^{\prime}\in[k]$ and
$j,j^{\prime}\in[n]$, where $i<i^{\prime}$ and $j<j^{\prime}$. The connector
gadget $S^{i,i^{\prime}}_{j,j^{\prime}}$ contains seven vertices
$\\{a_{1},a_{2},\cdots,a_{6}$, $s^{i,i^{\prime}}_{j,j^{\prime}}\\}$, where
$a_{5}$ is a special vertex. We add edges
$(a_{1},a_{2}),(a_{2},a_{3}),(a_{2},s^{i,i^{\prime}}_{j,j^{\prime}}),(a_{3},a_{5}),$
$(a_{3},s^{i,i^{\prime}}_{j,j^{\prime}}),(a_{4},s^{i,i^{\prime}}_{j,j^{\prime}}),(a_{4},a_{1}),(a_{4},a_{5})$
and $(a_{5},a_{6})$ to complete the connector gadget. See Figure 11. Moreover,
connect $S^{i,i^{\prime}}_{j,j^{\prime}}$ to the vertices $R$ and $B$, by
adding an edge between $a_{1}$ with $B$ and $a_{6}$ with $R$. The connector
gadget connects with grid vertices through $a_{1}$ and $a_{2}$. Connect the
vertices $a_{1}$ and $a_{2}$ in $S_{j,j^{\prime}}^{i,i^{\prime}}$ with
$p_{i^{\prime},d^{\prime}}$ and $p_{i,d}$ respectively, where
$d,d^{\prime}\in\\{j,j^{\prime}\\}$.

Furthermore, for all $i\in[k]$, we create a hanging gadget $\mathcal{H}_{i}$
with seven vertices, $\\{h_{i},h^{\prime}_{i},h^{\prime\prime}_{i},f_{i},$
$f^{\prime}_{i},d_{i},d^{\prime}_{i}\\}$. Two sets of vertices
$\\{h_{i},h^{\prime}_{i},h^{\prime\prime}_{i},f_{i}\\}$ and
$\\{h_{i},h^{\prime}_{i},h^{\prime\prime}_{i},f^{\prime}_{i}\\}$ form two
cycles with four vertices. The vertices $f_{i}$ and $f^{\prime}_{i}$ are
special vertices in $\mathcal{H}_{i}$. Connect $d_{i}$ and $d^{\prime}_{i}$
with $f_{i}$ and $f^{\prime}_{i}$ respectively. See Figure 9. In addition to
that, for every $h_{i}\in\mathcal{H}_{i}$, $1\leq i\leq k$ connect with grid
vertices $p_{i,j}$, for all $j\in[n]$.

Figure 10: Connector gadget

Figure 11: Selector gadget

Moreover, we add a selector gadget $\mathcal{Y}$ with a set of vertices
$Y=\\{y_{l}|1\leq l\leq t\\}$ and a set of four vertices $z_{1},\cdots,z_{4}$
such that $z_{2}$ is a special vertex. For all $l\in[t]$, we connect $y_{l}$
with $z_{1}$ and $z_{2}$. Additionally, add an edge between $z_{2}$ and
$z_{3}$. See Figure 11. The vertex $z_{4}$ is connected to $R$ and $B$. Here
the selector gadget $\mathcal{Y}$ intuitively shows which of the instances has
a clique of size $k$.

In addition to these edges, for every $l\in[t]$, $i,i^{\prime}\in[k]$, and
$j,j^{\prime}\in[n]$, add an edge $(s^{i,i^{\prime}}_{j,j^{\prime}},y_{l})$ if
and only if $(v_{j},v_{j^{\prime}})\in E(X_{l})$.

Now, we have completed the construction of graph $G$. The following lemmata
show the properties of the vertices in different gadgets and also help to
prove the correctness of the reduction.

###### Lemma 16

For any $2$-subset square colouring $C$ of $G$, $C(h_{i}),C(h^{\prime}_{i})$
and $C(h^{\prime\prime}_{i})$ will be $c_{0}$ for all values of $i\in[k]$.

###### Proof 9

For all $i\in[k]$, the vertices $f_{i}$ and $f^{\prime}_{i}$ are special
vertices and they are at distance two from each other. Therefore $f_{i}$ and
$f^{\prime}_{i}$ receive distinct colours. Since the vertices
$h_{i},h^{\prime}_{i}$, and $h^{\prime\prime}_{i}$ are distance at most $2$
from $f_{i}$ and $f^{\prime}_{i}$, we cannot colour them using red or blue.

We can observe from Lemma 16 that we cannot dominate the vertex $h_{i}$ by
colouring a vertex from $N[h_{i}]\cap\mathcal{H}_{i}$ and all other vertices
in $\mathcal{H}_{i}$ are dominated by at least one of the special vertices
$f^{\prime}_{i},f_{i}$.

###### Observation 17

For all $i\in[k]$, the grid vertices $\\{p_{i,j}|1\leq j\leq n\\}$ are
dominated by the vertex $r_{i}\in\mathcal{P}1_{i}$.

To dominate the vertex $h_{i}\in\mathcal{H}_{i}$, we need to colour a vertex
from grid vertices $\\{p_{i,j}|1\leq j\leq n\\}$. Since $r_{i}$ is coloured
using blue, we can colour exactly one vertex from the set $\\{p_{i,j}|1\leq
j\leq n\\}$ using red colour.

###### Lemma 18

For any $2$-subset square colouring $C$ of $G$, there exist distinct
$j_{1},\cdots,j_{k}$ such that $C(p_{i,j_{i}})=$ red and for every other grid
vertex $\\{p_{i,j_{t}}|1\leq t\leq n$ and $t\neq i\\}$,
$C(p_{i,j_{t}})=c_{0}$.

###### Proof 10

Let’s begin by showing that for every $i\in[k]$, there exist exactly one
$j\in[n]$ such that $C(p_{i,j})=$ red. Consider the hanging gadget, it is easy
to see that every vertex except $h_{i}$ in $\mathcal{H}_{i}$ are dominated by
the special vertices from $\mathcal{H}_{i}$ and $C(h_{i})=c_{0}$ by Lemma 16.
It follows that indeed $\\{p_{i,j}|1\leq j\leq n\\}$ contains at least one
coloured vertex. The colour of the vertex in $\\{p_{i,j}|1\leq j\leq n\\}$ is
red because $C(r_{i})=$ blue by Observation 17. Let $p_{i,j_{i}}$ be that
coloured vertex in $\\{p_{i,j}|1\leq j\leq n\\}$.

Now, we need to show that all $j_{i}$ are distinct. This can be proved by
showing that for each $j\in[n]$, there is exactly one $i\in[k]$ such that
$C(p_{i,j_{i}})=$ red. Consider the vertex $w_{j}$ in $\mathcal{P}2_{j}$,
observe that $N(w_{j})$ contains a blue vertex in $\mathcal{P}2_{j}$, it
follows that $w_{j}$ has a unique red neighbour, and thus there is exactly one
$i\in[k]$ such that $C(p_{i,j})=$ red. Observation 17 also shows that
$C(p_{i,j_{t}})=c_{0}$, where $t\neq i$.

Now, we can consider the connector gadget $S^{i,i^{\prime}}_{j,j^{\prime}}$,
that we created for every $p_{i^{\prime},d^{\prime}}$ and $p_{i,d}$, where
$d,d^{\prime}\in\\{j,j^{\prime}\\}$. The vertex $a_{6}$ is connected to the
vertex $R$ and $a_{5}$ is a special vertex, $C(a_{5})=$blue. The vertices
$a_{3},a_{4},a_{6}$ in $S^{i,i^{\prime}}_{j,j^{\prime}}$ are dominated by the
vertex $a_{5}$ and the vertex $a_{1}$ is dominated by $B$.

Now, the following observations show how to dominate the vertices $a_{2}$ and
$s^{i,i^{\prime}}_{j,j^{\prime}}$ in the connector gadget.

###### Observation 19

If there exists a subset square colouring $C$ such that neither
$C(p_{i,d})=$red nor $C(p_{i^{\prime},d^{\prime}})=$red, where
$d,d^{\prime}\in\\{j,j^{\prime}\\}$, then one of the following is true: $(a)$
$C(a_{2})=$ red or $(b)$ $C(a_{3})=$ red or $(c)$
$C(s^{i,i^{\prime}}_{j,j^{\prime}})=$red.

###### Proof 11

If colour of the vertices $p_{i,d}$ and $p_{i^{\prime},d^{\prime}}$ is
$c_{0}$, then to dominate the vertices $s^{i,i^{\prime}}_{j,j^{\prime}}$ and
$a_{2}$ in $S^{i,i^{\prime}}_{j,j^{\prime}}$, we can either colour the vertex
$a_{3}$ or $a_{2}$ or $s^{i,i^{\prime}}_{j,j^{\prime}}$. Since $C(a_{5})$ is
blue and $N[a_{1}]$ contains blue, we cannot colour any of these vertices
using blue (In Figure 12: Case 1 we coloured $a_{3}$).

###### Observation 20

If there exists a subset square colouring $C$ such that $C(p_{i,d})=c_{0}$,
$C(p_{i^{\prime},d^{\prime}})=$ red, then one of the following is true: $(a)$
$C(a_{3})=$red or $(b)$ $C(s^{i,i^{\prime}}_{j,j^{\prime}})=$ red.

###### Proof 12

To dominate the vertices $s^{i,i^{\prime}}_{j,j^{\prime}}$ and $a_{2}$, we can
either colour the vertex $a_{3}$ or $s^{i,i^{\prime}}_{j,j^{\prime}}$. Since
$e(a_{3},a_{5})$, $e(s^{i,i^{\prime}}_{j,j^{\prime}},a_{4})$ and
$e(a_{4},a_{5})$ exist, we cannot colour $a_{3}$ or
$s^{i,i^{\prime}}_{j,j^{\prime}}$ using blue.

###### Observation 21

If there exists a subset square colouring $C$ such that $C(p_{i,d})=$ red,
$C(p_{i^{\prime},d^{\prime}})=c_{0}$, then one of the following is true: $(a)$
$C(a_{4})=$ red or $(b)$ the edge $(s^{i,i^{\prime}}_{j,j^{\prime}},y_{l})$
exists (In Figure 12: Case 3 we coloured $a_{4}$) and $C(y_{l})=$ blue.

###### Proof 13

The vertex $a_{2}$ is dominated by $p_{i,d}$. Since $C(p_{i,d})$= red, we
cannot colour $a_{3}$ or $s^{i,i^{\prime}}_{j,j^{\prime}}$ to dominate the
vertex $s^{i,i^{\prime}}_{j,j^{\prime}}$. To dominate
$s^{i,i^{\prime}}_{j,j^{\prime}}$, we can either colour $a_{4}$ or add an edge
$(s^{i,i^{\prime}}_{j,j^{\prime}},y_{l})$.

###### Observation 22

If there exists a subset square colouring $C$ such that $C(p_{i,d})=$ red,
$C(p_{i^{\prime},d^{\prime}})=$ red under $C$, then the edge
$(s^{i,i^{\prime}}_{j,j^{\prime}},y_{l})$ exists.

###### Proof 14

If $C(p_{i,d})=$ red and $C(p_{i^{\prime},d^{\prime}})=$ red, then the vertex
$s^{i,i^{\prime}}_{j,j^{\prime}}$ cannot be colour using red. Since the vertex
$s^{i,i^{\prime}}_{j,j^{\prime}}$ is distance two from $a_{5}$, we cannot
colour the vertex $s^{i,i^{\prime}}_{j,j^{\prime}}$ using blue also. Therefore
edge $(s^{i,i^{\prime}}_{j,j^{\prime}},y_{l})$ exists to satisfy $2$-subset
square colouring. See Figure 12: Case 4.

Now, we can see that one vertex in $Y$ in the selector gadget must be coloured
in order to dominate the vertex $z_{1}$.

###### Lemma 23

For any $2$-subset square colouring $C$ of $G$, there exists exactly one
vertex in $Y$, $y_{l}\in\\{y_{i}|i\in[t]\\}$ such that $C(y_{l})=$ blue and
for every other vertex $y_{i}\in Y$, where $y_{i}\neq y_{l}\in Y$,
$C(y_{i})=c_{0}$.

###### Proof 15

The special vertex $z_{2}\in\mathcal{Y}$, is distance two from $B$. Therefore
$C(z_{2})=$ red. Every vertex in $\mathcal{Y}$, other than $z_{1}$ and $z_{4}$
is dominated by the special vertex $z_{2}$. Since the vertex $z_{4}$ is
connected to $B$ and $R$, we cannot dominate $z_{1}$ using $z_{1}$ or $z_{4}$.
Only a vertex $\\{y_{l}|l\in[t]\\}$ can dominate the vertex $z_{1}$, but every
$\\{y_{l}|1\leq l\leq t\\}$ is a neighbour of $z_{2}$. Therefore only one
vertex from $\\{y_{l}|l\in[t]\\}$ can dominate the vertex $z_{1}$, and the
colour of that vertex will be blue. Therefore for every other vertex $y\in Y$,
$C(y)=c_{0}$.

Figure 12: case analysis

Now, we claim the main lemma as follows.

###### Lemma 24

The graph $G$ is $2$-subset square colourable if and only if there exists
$l\in[t]$ such that instance $X_{l}$ has a clique of size $k$.

###### Proof 16

Assume there exists a YES instance $X_{l}$ such that it has a clique of size
$k$. Let $v_{l_{1}},\cdots,v_{l_{k}}\in V(X_{l})$ be the vertices that form a
clique in $X_{l}$. Now, for all $i\in[k],j\in[n]$, we colour the graph $G$ as
follows.

  1. 1.

Colour the vertices $R$ and $B$, such that $C(R)=$ red, and $C(B)=$ blue.

  2. 2.

Let $C(f_{i})=$ red and $C(f^{\prime}_{i})=$ blue (by Observation 14 and there
exist edges $(B,d_{i})$ and $(R,d^{\prime}_{i})$ in $G$).

  3. 3.

Since $w^{\prime\prime}_{j}$ is connected to $R$, $C(w^{\prime}_{j})=$ blue.

  4. 4.

$C(a_{5})=$ blue (by Observation 14 and $N(N(a_{5}))$ contains red colour).

  5. 5.

Since $z_{3}$ is connected to $B$, $C(z_{2})=$ red.

  6. 6.

Since $r^{\prime}_{i}$ is connected to $R$, $C(r_{i})=$ blue.

  7. 7.

Let $C(y_{l})=$ blue, ($y_{l}$ dominates the vertex $z_{1}$).

  8. 8.

Let $C(p_{i,l_{i}})=$ red for all $i\in[k]$ (dominates the vertex $h_{i}$) and
other vertices are coloured with $c_{0}$ (dominated by the vertex $r_{i}$) .

  9. 9.

If $C(p_{i,l_{i}})=c_{0}$ and $C(p_{i^{\prime},l_{i^{\prime}}})=c_{0}$ where
$d,d^{\prime}\in\\{j,j^{\prime}\\}$, then $C(a_{3})=$ red.

  10. 10.

If $C(p_{i,l_{i}})=c_{0}$ and $C(p_{i^{\prime},l_{i^{\prime}}})=$ red where
$d,d^{\prime}\in\\{j,j^{\prime}\\}$ then $C(a_{3})=$ red

  11. 11.

If $C(p_{i,l_{i}})=$ red and $C(p_{i^{\prime},l_{i^{\prime}}})=c_{0}$ where
$d,d^{\prime}\in\\{j,j^{\prime}\\}$, then $C(a_{4})=$ red.

Figure 13: Constructed graph $G$ with $k=4$, $n=5$ and $t=t$.

It is easy to verify that every vertex $v$ and $N[v]$ in $G$ satisfies the
$2$-subset square colouring constrains. Therefore this colouring in $G$ is a
valid $2$-subset square colouring. See Figure 13.

Now we can prove if $G$ can be $2$-subset square coloured under $C$, then
there exists $l\in[t]$ such that instance $X_{l}$ has a clique of size $k$.

From Lemma 23, we know that there exists one vertex in $Y$, with the colour
blue. Let $y_{l}$ be that vertex. By Lemma 18, there exist distinct
$j_{1},\cdots,j_{k}\in[n]$ such that $C(p_{i,j_{i}})=$ red. We will show that
the instance $X_{l}$ has a clique of size $k$, by proving that vertices
$v_{j_{1}},\cdots,v_{j_{k}}\in[n]$ form a clique in $X_{l}$. Assume that this
is not true. Then there exist $i,i^{\prime}\in[k]$ such that $v_{j_{i}}$ and
$v_{j_{i^{\prime}}}$ are not connected by an edge in $X_{l}$. This leads to a
contradiction. Now, consider the connector gadget
$S^{i,i^{\prime}}_{j_{i},j^{\prime}_{i}}$, the vertices
$p_{i^{\prime},l_{i^{\prime}}}$ and $p_{i,l_{i}}$ are coloured with red. Since
the vertex $s^{i,i^{\prime}}_{j,j^{\prime}}$ is distance two from $a_{5}$ and
$p_{i,l_{i}}$, we cannot colour the vertex $s^{i,i^{\prime}}_{j,j^{\prime}}$
using red or blue. Therefore the edge
$(s^{i,i^{\prime}}_{j,j^{\prime}},y_{l})$ exists to dominate
$s^{i,i^{\prime}}_{j,j^{\prime}}$.

To prove the lower bound, it remains to bound the size of a vertex cover in
$G$. Since vertices in $Y$ form an independent set in $G$, it follows that
$V(G)\backslash(Y=\\{y_{l}|1\leq l\leq t\\})$ is a vertex cover of $G$.

The number of grid vertices in $G$ is $nk$, and corresponding to every pair of
vertices in grid there exists a connector gadget. Therefore the total number
of vertices in connector gadgets is $7(n^{2}k^{2})$. All other vertices in $G$
are linearly bounded by $n$ and $k$. Therefore $|V(G)\backslash
Y|=O(n^{2}k^{2})$. Thus we have proved the following theorem.

###### Theorem 25

$2$-subset square colouring problem parameterized by the size of vertex cover
does not have a polynomial kernel.

####  4.3.2 Kernalization: $q$-Subset Square Colouring problem parameterized
by the size of vertex cover, where $q\geq 3$.

In this section we extend the result for $q\geq 3$ by modifying the gadgets in
$G$ and the definition of a special vertex as follows. In this section, we
assume that $c_{1}=$ red and $c_{2}=$ blue.

Special vertex : If a vertex $v$ is a special vertex, then $N(v)$ contains
$q+1$ single degree vertices.

###### Observation 26

For any $q$-subset square colouring $C$ of $G$, if a vertex $v$ in $G$ is a
special vertex, then $C(v)\neq c_{0}$.

We add a set of special vertices $Q=\\{Q_{1},Q_{2},\cdots Q_{q}\\}$ such that
they form a clique in $G$. Therefore all the vertices in $Q$ are coloured
using different colours. Without loss of generality, assume that
$C(Q_{1})=c_{1}$, $C(Q_{2})=c_{2}$ and so on. We modify the gadgets used in
Section 4.3.1 as follows.

For every $i\in[k]$, we add a path gadget $\mathcal{P}1_{i}$ with three
vertices $r^{\prime}_{i},r_{i},$ and $r^{\prime\prime}_{i}$. In every
$\mathcal{P}1_{i}$, there exist edges $(r^{\prime}_{i},r_{i})$ and
$(r_{i},r^{\prime\prime}_{i})$, where $r_{i}$ is a special vertex. We connect
path gadget $\mathcal{P}1_{i}$ to the set of vertices in $Q$, by adding edges
between $r_{i}$ and every vertex from the set $\\{Q_{3},Q_{4}\cdots Q_{q}\\}$.
Also, add an edge $(r^{\prime\prime}_{i},Q_{1})$. See Figure 16. Moreover
$\mathcal{P}1_{i}$ connects to grid vertices through $r_{i}$ by adding edges
$(r_{i},p_{i,j})$, for all $j\in[n]$.

For every $j\in[n]$, we use a path gadget, $\mathcal{P}2_{j}$ ,with three
vertices $w_{j}$, $w^{\prime}_{j}$ and $w^{\prime\prime}_{j}$. In every
$\mathcal{P}2_{j}$, there exist edges $(w_{j},w^{\prime}_{j})$ and
$(w^{\prime}_{j},w^{\prime\prime}_{j})$, where $w^{\prime}_{j}$ is a special
vertex. We add a vertex $w$ and connect path gadget $\mathcal{P}2_{j}$ to the
set of vertices in $Q$, by adding edges between $w_{j}$ and every vertex from
the set $\\{Q_{3},Q_{4}\cdots Q_{q}\\}$. Add an edge $(w_{j},w)$ and add edges
between $w$ and every vertex from the set $\\{Q_{x}\in Q|1\leq x\leq q$ and
$x\neq 2\\}$. See Figure 16.

###### Observation 27

For any $q$-subset square colouring $C$ of $G$, for all $i\in[k],j\in[n]$,
$C(r_{i})=$ blue and $C(w^{\prime}_{j})=$ blue and all other vertices in path
gadgets $\mathcal{P}1_{i}$ and $\mathcal{P}2_{j}$ are dominated by $r_{i}$ and
$w^{\prime}_{j}$, respectively.

Figure 14: Path gadget $\mathcal{P}1_{i}$ connected with set of vertices in
$Q$

Figure 15: Path gadget $\mathcal{P}2_{j}$ connected with set of vertices in
$Q$

Figure 16: Selector gadget

We modify the connector gadget as follows. For every $i,i^{\prime}\in[k]$ and
$j,j^{\prime}\in[n]$ in $S^{i,i^{\prime}}_{j,j^{\prime}}$, where
$i<i^{\prime}$ and $j<j^{\prime}$, the gadget
$S^{i,i^{\prime}}_{j,j^{\prime}}$ contains the set of vertices
$\\{a_{1},a_{2},a_{3}$, $s^{i,i^{\prime}}_{j,j^{\prime}}\\}$,
$\\{a^{1}_{4},a^{2}_{4},\cdots a^{q-1}_{4}\\}$, $\\{a^{1}_{5},a^{2}_{5},\cdots
a^{q-1}_{5}\\}$, and $\\{a^{1}_{6},a^{2}_{6},\cdots a^{q-1}_{6}\\}$. Note that
all $a^{x}_{5}$ are special vertices in $S^{i,i^{\prime}}_{j,j^{\prime}}$,
where $1\leq x\leq q-1$.

We add edges
$(a_{1},a_{2}),(a_{2},a_{3}),(a_{2},s^{i,i^{\prime}}_{j,j^{\prime}}),$ and
$(a_{3},s^{i,i^{\prime}}_{j,j^{\prime}})$ in the connector gadget. For every
$1\leq x\leq q-1$, add edges between $a^{x}_{4}$ with the vertices
$s^{i,i^{\prime}}_{j,j^{\prime}}$ and $a_{1}$. In addition to that, for every
$1\leq x\leq q-1$, add edges between $a^{x}_{4}$ and $a^{x}_{5}$. For every
$1\leq x\leq q-1$, add edges between $a^{x}_{5}$ and $a_{3}$. Also, for every
$1\leq x\leq q-1$, we add edges between $a^{x}_{6}$ and $a^{x}_{5}$.

Connect $S^{i,i^{\prime}}_{j,j^{\prime}}$ to the set of vertices in $Q$, by
adding an edge between $a_{1}$ and all the vertices in $Q$ except $Q_{1}$. For
every $1\leq x\leq q-1$, we connect $a^{x}_{6}$ with all vertices in $Q$
except the vertex $Q_{x+1}$. See Figure 18. The connector gadget connects with
grid vertices through $a_{1}$ and $a_{2}$. Connect the vertices $a_{1}$ and
$a_{2}$ in $S_{j,j^{\prime}}^{i,i^{\prime}}$ with $p_{i^{\prime},d^{\prime}}$
and $p_{i,d}$ respectively, where $d,d^{\prime}\in\\{j,j^{\prime}\\}$.

Figure 17: Connector gadget connected with a set of vertices in $Q$

Figure 18: Hanging gadget connected with a set of vertices in $Q$

Furthermore, for all $i\in[k]$, we modify the hanging gadget as follows. In
this proof the hanging gadget $\mathcal{H}_{i}$ contains the set of vertices,
$\\{h_{i},h^{\prime}_{i},h^{\prime\prime}_{i}\\}$,
$\\{f^{1}_{i},f^{2}_{i}\cdots f^{q}_{i}\\}$ and $\\{d^{1}_{i},d^{2}_{i}\cdots
d^{q}_{i}\\}$, where all $f^{x}_{i}$, $1\leq x\leq q$ are special vertices in
$\mathcal{H}_{i}$. For all $i\in[k]$, these sets of vertices
$\\{h_{i},h^{\prime}_{i},h^{\prime\prime}_{i},f^{x}_{i}\\}$ form $q$ cycles
with four vertices, where $1\leq x\leq q$. For every $1\leq x\leq q$,
$d^{x}_{i}$ has an edge with $f^{x}_{i}$. The hanging gadget $\mathcal{H}_{i}$
is connected to the set of vertices in $Q$, by adding edges between
$d^{x}_{i}$ and $Q_{x}\in Q$, for all $1\leq x\leq q$. See Figure 18. In
addition, every $h_{i}$ connects with grid vertices $p_{i,j}$, for all
$j\in[n]$.

Furthermore, we modify the selector gadget $\mathcal{Y}$ as follows. The
selector gadget $\mathcal{Y}$, contain a set of vertices $Y=\\{y_{l}|1\leq
l\leq t\\}$ and four vertices $z_{1},\cdots,z_{4}$, where $z_{2}$ is a special
vertex. For all $l\in[t]$, we connect $y_{l}$ with $z_{1}$ and $z_{2}$. The
vertex $z_{4}$ is connected to $z_{1}$. Additionally, add an edge between
$z_{2}$ and $z_{3}$. Connect the selector gadget to the set of vertices in
$Q$, by adding an edge$(z_{3},Q_{2})$ and by connecting the vertex $z_{2}$
with all $Q_{x}\in Q$, where $3\leq x\leq q$. In addition to these edges,
connect $z_{4}$ with all vertices from the set $Q$. See Figure 16.

###### Lemma 28

For any $q$-subset square colouring $C$ of $G$, $C(h_{i}),C(h^{\prime}_{i})$
and $C(h^{\prime\prime}_{i})$ will be $c_{0}$ for all values of $i\in[k]$.

###### Proof 17

For all $i\in[k]$, the vertices $f^{x}_{i}$, where $1\leq x\leq q$ are special
vertices, and they are at distance two from each other. Therefore all
$f^{x}_{i}$ receive distinct $q$ colours. Since the vertices
$h_{i},h^{\prime}_{i}$, and $h^{\prime\prime}_{i}$ are distance at most $2$
from $f^{x}_{i}$, we cannot colour them.

We can observe from Lemma 28 that we cannot dominate the vertex $h_{i}$ by
colouring a vertex from $N[h_{i}]\cap\mathcal{H}_{i}$ and all other vertices
in $\mathcal{H}_{i}$ are dominated by at least one of the special vertices
$f^{x}_{i}$. Without loss of generality, assume that $C(f^{x}_{i})=c_{i+1}$,
where $1\leq x\leq q-1$ and $C(f^{x}_{q})=c_{1}$.

###### Observation 29

For all $i\in[k]$, the grid vertices $\\{p_{i,j}|1\leq j\leq n\\}$ are
dominated by the vertex $r_{i}\in\mathcal{P}1_{i}$.

To dominate the vertex $h_{i}\in\mathcal{H}_{i}$, we need to colour a vertex
from grid vertices $\\{p_{i,j}|1\leq j\leq n\\}$. Since $r_{i}$ is coloured
using blue and $r_{i}$ is connected with all vertices in $Q$ except $Q_{1}$,
we can colour exactly one vertex from the set $\\{p_{i,j}|1\leq j\leq n\\}$
using red colour.

###### Lemma 30

For any $q$-subset square colouring $C$ of $G$, there exist distinct
$j_{1},\cdots j_{k}$ such that $C(p_{i,j_{i}})=$ red and for every other grid
vertex $\\{p_{i,j_{t}}|1\leq t\leq n$ and $t\neq i\\}$,
$C(p_{i,j_{t}})=c_{0}$.

###### Proof 18

Let’s begin by showing that for every $i\in[k]$, there exists exactly one
$j\in[n]$ such that $C(p_{i,j})=$ red. Consider the hanging gadget, it is easy
to see that every vertex except $h_{i}$ in $\mathcal{H}_{i}$ is dominated by
the special vertices from $\mathcal{H}_{i}$ and $C(h_{i})=c_{0}$ by Lemma 28.
It follows that indeed $\\{p_{i,j}|1\leq j\leq n\\}$ contains at least one
coloured vertex. The colour of the vertex in $\\{p_{i,j}|1\leq j\leq n\\}$ is
red because $C(r_{i})=$ blue and there exists edges $(r_{i},Q_{x})$, where
$3\leq x\leq q$ by Observation 29. Let $p_{i,j_{i}}$ be that coloured vertex
in $\\{p_{i,j}|1\leq j\leq n\\}$.

Now, we need to show that all $j_{i}$ are distinct. This can be proved by
showing that for each $j\in[n]$, there is at most one $i\in[k]$ such that
$C(p_{i,j_{i}})=$ red. Consider the vertex $w_{j}$ in $\mathcal{P}2_{j}$,
observe that $N(w_{j})$ contains all $q$ coloured vertices except red, it
follows that $w_{j}$ has a unique red neighbour, and thus there is exactly one
$i\in[k]$ such that $C(p_{i,j})=$ red. This also shows that
$C(p_{i,j_{t}})=c_{0}$, where $t\neq i$.

Now we can consider the connector gadget $S^{i,i^{\prime}}_{j,j^{\prime}}$
that corresponds to $p_{i^{\prime},d^{\prime}}$ and $p_{i,d}$ where
$d,d^{\prime}\in\\{j,j^{\prime}\\}$ For every $1\leq x\leq q$, $a^{x}_{6}$ is
connected to all vertices in $Q$ except $Q_{x+1}$ and all $a^{x}_{5}$ are
special vertices, $C(a^{x}_{5})=c_{x}$. The vertices
$a_{3},a^{x}_{4},a^{x}_{6}$ in $S^{i,i^{\prime}}_{j,j^{\prime}}$ are dominated
by the vertices $a^{x}_{5}$ and the vertex $a_{1}$ is dominated by $B$.

Now, we can see that the colours admissible to connector gadget, selector
gadget, and grid vertices are red and blue. Therefore the following lemma can
be proved using arguments those given in Section 4.3.1.

Now, we can see that one vertex in $Y$ in the selector gadget must be
coloured, in order to dominate the vertex $z_{1}$.

###### Lemma 31

For any $q$-subset square colouring $C$ of $G$, there exists exactly one
vertex in $Y$, $y_{l}\in\\{y_{i}|i\in[t]\\}$ such that $C(y_{l})=$ blue and
for every other vertex $y_{i}\in Y$, where $y_{i}\neq y_{l}\in Y$,
$C(y_{i})=c_{0}$.

###### Proof 19

The special vertex $z_{2}\in\mathcal{Y}$, is distance two from all the
vertices of $Q$ except $Q_{1}$. Therefore $C(z_{2})=$ red. Every vertex in
$\mathcal{Y}$, other than $z_{1}$ and $z_{4}$ are dominated by the special
vertex $z_{2}$. Since the vertex $z_{4}$ is connected to all vertices in $Q$,
we cannot dominate $z_{1}$ using $z_{1}$ or $z_{4}$. Only a vertex
$\\{y_{l}|l\in[t]\\}$ can dominate the vertex $z_{1}$, but every
$\\{y_{l}|1\leq l\leq t\\}$ is a neighbour of $z_{2}$. Therefore only one
vertex from $\\{y_{l}|l\in[t]\\}$ can dominate the vertex $z_{1}$, and the
colour of that vertex will be blue. Therefore for every other vertex $y\in Y$,
$C(y)=c_{0}$.

By arguments similar to those given in proof of Lemma 24, we can see the
following lemma.

###### Lemma 32

The graph $G$ is $q$-subset square colourable if and only if there exists
$l\in[t]$ such that instance $X_{l}$ has a clique of size $k$.

Now, there exists a $|V(G)\backslash Y|=O(qn^{2}k^{2})$. Thus we have proved
the following theorem.

###### Theorem 33

$q$-Subset Square Colouring problem parameterized by the size of vertex cover
does not have a polynomial kernel for $q\geq 3$ using OR-cross composition
from the Clique problem.

###  4.4 Parameterized by neighbourhood diversity

We start by defining the neighbourhood diversity of a graph.

###### Definition 5

[22] Given a graph $G=(V,E)$, two vertices $u,v\in V$ have the same type if
and only if $N(v)\backslash\\{u\\}=N(u)\backslash\\{v\\}$. The graph $G$ has a
neighbourhood diversity t, if there exists a partition of $V$ into at most $t$
sets, $V_{1},V_{2},\dots,V_{t}$ such that all the vertices in $V_{i}$ have the
same type for $i=1,2,\dots,t$. The family $\nu=\\{V_{1},V_{2},\dots,V_{t}\\}$
is called the type partition of $G$.

On creating such a type partition of $V(G)$, we observe that the vertices
within a partition either induces a clique or is an independent set. Further,
for $1\leq i,j\leq t$, each vertex in a partition $V_{i}$ is either adjacent
to every vertex in another partition $V_{j}$ or there are no edges between
vertices of $V_{i}$ and $V_{j}$.

###### Lemma 34

The number of colours required to subset square colour a graph $G$ is at most
its neighbourhood diversity, that is, $\chi_{ssc}(G)\leq t$.

###### Proof 20

For a given graph $G$, consider its type partition $\nu$ with neighbourhood
diversity $t$. Colour all isolated vertices, if any, using one of the $t$
colours. For $1\leq i\leq t$, colour a vertex in each $V_{i}$ using a
different colour. This gives us a subset square colouring of $V(G)$. This can
be justified as follows. Vertices in partitions $V_{i}$ that form a clique are
all dominated due to the presence of a coloured neighbour in $V_{i}$.
Additionally, if vertices of $V_{i}$ are adjacent to partition $V_{j}$ for
$1\leq j\leq t$, we can expect them to be adjacent to some more coloured
neighbours. Now consider the case where vertices in partition $V_{i}$ form an
independent set, then they will be adjacent to all vertices of at least one
other partition $V_{j}$ which assures the presence of at least one coloured
neighbour in the closed neighbourhood of each vertex in $V_{i}$. Moreover, no
colour is repeated in the colouring of any connected component and we have
used $t$ number of colours to subset square colour $G$. Hence the result
follows.

Now we show that $q$-Subset Square Colouring parameterized by $t$ is FPT by
giving a polynomial kernel.

###### Theorem 35

The $q$-Subset Square Colouring problem parameterized by neighbourhood
diversity admits a polynomial kernel of size $O(t^{2})$.

###### Proof 21

Let $G$ be a connected graph, along with a type partition of size $t$, $t>1$.
Let $G^{\prime}(V^{\prime},E^{\prime})$ be the graph obtained from $G(V,E)$ by
deleting all but $q+1$ vertices from each type partition. We will show that
$G^{\prime}$ can be $q$-subset square coloured if and only if $G$ can be
$q$-subset square coloured. Note that $G^{\prime}$ is also a connected graph.

Let $\chi$ be a $q$-subset square colouring of $G^{\prime}$. We claim $\chi$
is a $q$-subset square colouring of $G$ as well. Let
$V_{i}^{\prime}=\\{v_{1},v_{2},\cdots,v_{q+1}\\}$ be a vertex set in the type
partition of $V(G^{\prime})$. If $v_{i}$ and $v_{j}$, $1\leq i,j\leq q+1,i\neq
j$, are coloured, then $\chi(v_{i})\neq\chi(v_{j})$. Otherwise, there exists
at least one common neighbour for all vertices in $V_{i}^{\prime}$, since
$G^{\prime}$ is connected and this is a contradiction. Since there are at most
$q$ colours, there exists at least one uncoloured vertex, say $v_{i}$ in
$V_{i}^{\prime}$. Now, every vertex in $V_{i}\setminus V_{i}^{\prime}$ is
dominated in $G$ by the same vertices that dominate $v_{i}$ in $G^{\prime}$.

In the reverse direction, assume that $G$ admits a $q$-subset square
colouring, $\chi$. Then we colour the vertices $v_{1},v_{2},\cdots,v_{q+1}$ in
$V_{i}^{\prime}$ arbitrarily using the colours, if any, used by $\chi$ on
$V_{i}$. Now it is easy to see that this is a valid $q$-subset square
colouring for $G^{\prime}$ as well.

Now $|V(G^{\prime})|\leq(q+1)t$. If $q\geq t$, the problem is trivially a YES
instance, by Lemma 34. Therefore $|V(G^{\prime})|=O(t^{2})$. Now the result
follows.

###  4.5 Parameterized by distance to cluster graph

###### Definition 6

A cluster graph is a disjoint union of complete graphs.

It is easy to see that cluster graphs can be $1$-subset square coloured.

###### Definition 7

A cluster vertex deletion set $X$ of a graph $G$ is a set of vertices such
that $G\backslash X$ forms a cluster graph.

The cluster vertex deletion number is defined as the minimum possible size of
a cluster vertex deletion set $X$. Intuitively, it is the measure of how close
a graph is to being a cluster graph.

In this section, let $X$ be the subset of $V(G)$ such that $G[V\setminus X]$
is a cluster graph and $|X|=k$. Now we observe the connection between
$\chi_{ssc}(G)$ and $k$.

###### Lemma 36

$\chi_{ssc}(G)\leq|X|+1$.

###### Proof 22

To subset square colour graph $G$, we colour every vertex $v\in X$ using $k$
different colours. Now, for every complete sub-graph in $G\backslash X$,
colour exactly one of the undominated vertices(if exists), using a colour that
is different from previously used $k$ colours. Note that two coloured vertices
$u$ and $v$ in two different complete sub-graphs do not have a common
neighbour in $X$ because in such a scenario, we would not choose either of $u$
or $v$ to be coloured. We assign the $(k+1)^{th}$ colour only to a vertex not
adjacent to any coloured vertex in $X$. This gives us a subset square
colouring of $G$ as the vertices in $X$ are dominated by the colours assigned
to them. Additionally, some of the vertices in $G\backslash X$ may also have a
neighbour in $X$. Every $v\in V(G)$ has at least one coloured neighbour in
$N[v]$ and in case more than one coloured vertices are present in $N[v]$, we
are assured of them being distinct because we have used $k+1$ colours.
Therefore the result follows.

###### Theorem 37

The $q$-Subset Square Colouring is FPT when parameterized by distance to
cluster graph.

###### Proof 23

If $q\geq|X|+1$, then by Lemma 36 it is trivially true that a subset square
colouring exists. Therefore, we assume that $q\leq k$.

If two or more vertices in a clique in $G[V\setminus X]$ have the same
neighbourhood in $X$, delete all but one of those vertices. This does not
affect the solution as the closed neighbourhood of the vertices are the same.
Therefore every clique in $G[V\setminus X]$ has at most $2^{k}$ vertices.

Now we bound the number of cliques in $G[V\setminus X]$. Let
$\\{\mathcal{X}_{1},\mathcal{X}_{2},\dots,\mathcal{X}_{2^{k}}\\}$ be the
family of subsets of $X$. For two cliques $C_{a}$ and $C_{b}$ in $G[V\setminus
X]$, we say $C_{a}$ and $C_{b}$ have the same _type_ if for all $1\leq i\leq
2^{k}$, either both $C_{a}$ and $C_{b}$ each have a vertex whose neighbourhood
in $X$ is $\mathcal{X}_{i}$ or neither of them has such a vertex. Note that
there can be at most $2^{2^{k}}$ distinct types of cliques. Now we use the
following reduction exhaustively to get a reduced graph $G^{\prime}$. If there
exists more than $q2^{k}+1$ cliques of the same type, delete all but
$q2^{k}+1$ of them. Thus there are at most $k+2^{2^{k}}\cdot(q2^{k}+1)$
vertices in $G^{\prime}$.

We claim that $G$ has a $q$-subset square colouring if and only if
$G^{\prime}$ has a $q$-subset square colouring. Assume $G^{\prime}$ admits a
$q$-subset square colouring. Let $C_{i}$ be a clique in $G\setminus
G^{\prime}$. Therefore $G^{\prime}$ has $(q2^{k}+1)$ cliques of the same type
as $C_{i}$, let them be
$C^{\prime}_{1},C^{\prime}_{2},\dots,C^{\prime}_{q2^{k}+1}$. Similarly, for
$v\in V(C_{i})$, there exists $v_{j}\in V(C^{\prime}_{j})$ for all $1\leq
j\leq q2^{k}+1$ such that $N(v)\cap X=N(v_{j})\cap X$. We show that there
exists at least one $C^{\prime}_{j}$ such that one of the conditions is true.

  * 1.

$C^{\prime}_{j}$ contains a vertex $v_{j}$ such that $N(v_{j})\cap
X=\emptyset$ and $v_{j}$ is coloured.

  * 2.

None of the vertices in $C^{\prime}_{j}$ is coloured.

If the first condition is true, then we can dominate all vertices in $C_{i}$
by colouring the corresponding vertex $v$ using the same colour as $v_{j}$.
Now, assume that the first condition is not true. Consider the vertices
$v_{j}\in V(C^{\prime}_{j})$ for all $1\leq j\leq q2^{k}+1$. Since all of them
have common neighbours in $X$, we can colour at most $q$ such vertices. Since
there are at most $2^{k}$ vertices in a clique, there can be at most $q2^{k}$
cliques with coloured vertices. All the uncoloured vertices in a clique is
dominated by vertices in $X$. The same set of vertices can dominate the
vertices in $C^{\prime}_{j}$ in $G$. The other direction is easy to see.

Since the size of the reduced instance is bounded by a function of $k$, it
follows that the $q$-Subset Square Colouring is FPT when parameterized by
distance to cluster graph.

###  4.6 Parameterized by the size of twin cover

###### Definition 8

[20] For a graph $G(V,E)$ a subset $X$ of vertices is a _twin cover_ if for
every edge $e=uv\in E(G)$ either $(a)$ $u\in X$ or $v\in X$, or $(b)$ $u$ and
$v$ are true twins.

Two vertices $u$ and $v$ are true twins if every other vertex is either
adjacent to both $u$ and $v$ or neither of them and $u$ and $v$ has an edge
between them. It follows from the definition that if $X$ is a twin cover, then
$G[V\setminus X]$ is a disjoint union of cliques and for every vertex $v\in X$
and every clique in $G[V\setminus X]$, $v$ is either adjacent to every vertex
in the clique or $v$ is not adjacent to any vertex in the clique. Thus for
every graph $G$, distance to cluster graph of $G$ $\leq$ size of twin cover
$\leq$ size of vertex cover. Thus it follows from Theorem 37 that the
$q$-Subset Square Colouring problem parameterized by twin cover is FPT. Here,
we give an algorithm with a better running time.

###### Theorem 38

The $q$-Subset Square Colouring problem parameterized by the size of twin
cover is FPT.

###### Proof 24

Let $X\subset V$ be a twin cover of the graph $G(V,E)$ and $|X|=k$. It can be
seen that $\chi_{ssc}(G)\leq|X|$. If $q\geq k$, then return $TRUE$. Now, we
assume that $q<k$.

Consider all possible ${(q+1)}^{k}$ colourings of $X$ using
$\\{c_{0},c_{1},\dots c_{q}\\}$. Let $\chi$ be such a colouring of $X$ such
that no vertex in $V$ has the same colour repeated in its closed
neighbourhood. We say a colouring $\chi_{G}$ of $V$ _extends_ $\chi$ if
$\chi_{G}$ restricted to $X$ is $\chi$. Our algorithm tries to extend each of
the colourings to a valid $q$-subset square colouring of $G$ as follows.

In each clique in $G[V\setminus X]$, we can retain a single vertex and delete
all others since all the vertices in the clique are adjacent to the same set
of vertices in $X$. Now we can observe that every vertex in $G[V\setminus X]$
is independent.

Let $I=V\setminus X$. Let $W\subseteq I$ be the set of vertices that are not
dominated by $\chi$. Note that in a valid subset square colouring of $G$ that
extends $\chi$, these vertices are coloured since $I$ induces an independent
set in $G$. Observe that any $v\in X$ can have at most $q$ such neighbours in
$W$, because each of them needs to be coloured using a distinct colour.

The number of vertices in $W$ is therefore bounded by $kq$ which is at most
$k^{2}$ as $q\leq k$. We can now colour the vertices in $W$ in
$\mathcal{O}(k^{k^{2}})$ time using brute force. We will now be left with
vertices in $X$ that are not dominated. We call the set of neighbours of such
vertices in $I$ as $U$. Now if two or more vertices in $U$ have the same
neighbourhood in $X$, then we retain exactly one such vertex in $U$ and delete
others. This does not affect the solution since the deleted vertices are
already dominated and any deleted vertex can dominate the same set of vertices
as the retained vertex. Thus $U$ has at most $2^{k}$ vertices which we can
colour in $\mathcal{O}(q^{2^{k}})$ or $\mathcal{O}(k^{2^{k}})$ time as $q\leq
k$. Hence the running time of the algorithm is $\mathcal{O}(k^{2^{k}})$.

###  4.7 Parameterized by modular width

We start by showing the connection between $\chi_{ssc}(G)$ and the modular
width of the graph. We first define the modular width of a graph. The modular
width of graph $G$ is computed by virtue of four operations, namely creation
of isolated vertex, disjoint union, complete join and substitution. More
precisely, the modular width of $G$ equals the maximum number of operands used
by any occurrence of substitution operation. These four operations that are
involved in the modular decomposition of graph $G$ are described in [19]. For
the sake of completeness, we mention the four operations here.

###### Definition 9

[19] Algebraic operations involved to compute modular width of graph $G$.

  * 1.

Create an isolated vertex;

  * 2.

The disjoint union of two graphs, i.e., the disjoint union of two graphs
$G_{1}$ and $G_{2}$, denoted by $G_{1}\otimes G_{2}$, is the graph with vertex
set $V(G_{1})\cup V(G_{2})$ and edge set $E(G_{1})\cup E(G_{2})$;

  * 3.

The complete join of two graphs, i.e., the complete join of two graphs $G_{1}$
and $G_{2}$, denoted by $G_{1}\oplus G_{2}$, is the graph with vertex set
$V(G_{1})\cup V(G_{2})$ and edge set $E(G_{1})\cup
E(G_{2})\cup\\{\\{v,u\\}:v\in V(G_{1})$ and $u\in V(G_{2})\\}$.

  * 4.

The substitution operation with respect to some graph $G^{\prime}$ with
vertices $v_{1},\dots,v_{n}$, i.e., for graphs $G_{1},\dots,G_{n}$ the
substitution of the vertices of $G^{\prime}$ by the graphs
$G_{1},\dots,G_{n}$, denoted by $G^{\prime}(G_{1},\dots,G_{n})$, is the graph
with vertex set $\underset{1\leq i\leq n}{\cup}V(G_{i})$ and edge set
$\underset{1\leq i\leq n}{\cup}E(G_{i})\cup\\{\\{u,v\\}:u\in V(G_{i})$ and
$v\in V(G_{j})$, $v_{i},v_{j}\in E(G^{\prime})$ and $i\neq j\\}$. Hence,
$G^{\prime}(G_{1},\dots,G_{n})$ is obtained from $G^{\prime}$ by substituting
every vertex $v_{i}\in V(G^{\prime})$ with the graph $G_{i}$ and adding all
edges between the vertices of a graph $G_{i}$ and the vertices of a graph
$G_{j}$ whenever $\\{v_{i},v_{j}\\}\in E(G^{\prime})$.

###### Definition 10

[19] Let $A$ be an algebraic expression that uses only the four operations as
mentioned in Definition 9. We define the width of $A$ as the maximum number of
operands used by any occurrence of the substitution operation in $A$. The
modular width of graph G, denoted as $w(G)$, is the least integer $m$ such
that $G$ can be obtained from such an algebraic expression of width at most
$m$.

Cographs are the graphs that can be constructed from operations$-$creation of
an isolated vertex, disjoint union of two graphs and complete join of two
graphs. By definition, the modular width of cographs is two [14].

Now we state our result for the optimal algorithm as well as bounds, by
bounding the number of colours used in each subgraph which is generated by one
of the operations defined in 9.

###### Lemma 39

The maximum number of colours required to subset square colour a graph $G$
equals the modular width of $G$, that is, $\chi_{ssc}(G)\leq w(G)$.

###### Proof 25

Now we discuss the maximum number of colours required to subset square colour
$G$ while we perform those operations. On introducing an isolated vertex, we
colour it by using one colour. To dominate the vertices created as a result of
the disjoint union of two graphs, we can use the maximum number of colours
that were used in subset square colouring each subgraph in the disjoint union
operation. Now we consider the complete join operation on the subgraph
$G_{c}$. Let $G_{c}=G_{c1}\otimes G_{c2}$. If a vertex $v$ in $V(G_{ci})$,
$i=\\{1,2\\}$ has degree $|G_{i}(V)|-1$, then $\chi_{ssc}(G_{c})=1$.
Otherwise, we can colour an arbitrary vertex $v$ from each $G_{c1}$ and
$G_{c2}$ using two distinct colours. Therefore the value of $\chi_{ssc}$ is
$\leq 2$. Finally, we examine the substitution operation. We colour an
arbitrary vertex $v$ in each $G_{i}$ using distinct colours. Now, for every
vertex in $G_{i}$ is adjacent to another coloured vertex in $G_{j}$, where
$j\neq i$. Therefore the value of $\chi_{ssc}$ can be at most $w$.

###### Theorem 40

The $q$-Subset Square Colouring is FPT when parameterized by modular width.

###### Proof 26

Let $G$ be a graph of modular width $w$. We know that $G$ can be built in a
hierarchical fashion, using the operations defined in Definition 9. Our
algorithm computes the optimal subset square colouring for each intermediate
subgraph created by each operation, thus eventually computing the optimal
subset square colouring for $G$. Further, for each subgraph, the algorithm
maintains the size of the minimum dominating set for the subgraph.

The optimum number of colours needed to dominate a subgraph is one if the
subgraph contains only isolated vertices. The minimum dominating set of this
subgraph contains all the vertices. Now, consider the operation,
$G_{d}=G_{d1}\otimes G_{d2}$. The optimum number of colours needed on $G_{d}$
is $max\\{$optimum number of colours used on$(G_{d1})$, optimum number of
colours used on$(G_{d2})\\}$. The minimum dominating set for $G_{d}$ is the
union of minimum dominating sets of $G_{d1}$ and $G_{d2}$. Now, we consider a
subgraph $G_{c}$ created by complete join operation, $G_{c}=G_{c1}\oplus
G_{c2}$. If a vertex $v$ in $V(G_{ci})$, $i=\\{1,2\\}$ has degree
$|G_{i}(V)|-1$, then the optimum number of colours used on this node is $1$.
Otherwise, we colour one arbitrary vertex $v$ from each graph. Therefore the
optimum number of colours used in this node is either $1$ or $2$. Here, the
size of the minimum dominating set is same as the optimum number of colours
used.

Now we consider the substitution operation on $G^{\prime}$. In this operation,
we replace each vertex $v_{i}\in V(G^{\prime})$ with the subgraph $G_{i}$, for
$1\leq i\leq w$. Therefore the vertices in $G^{\prime}$ are in one-to-one
correspondence with the subgraphs $G_{i}$. Consider the optimal subset-square
colouring $\chi$ of $G$. We guess the colouring $\chi^{\prime}$ of
$G^{\prime}$ that corresponds to $\chi$ as follows : The vertex $v_{i}\in
V(G^{\prime})$ is coloured by $\chi^{\prime}$ if $G_{i}$ contains coloured
vertices under $\chi$. Moreover $\chi^{\prime}(v_{i})$ is one of the colours
used by $\chi$ in $G_{i}$. Also, $v_{i}$ is not coloured by $\chi^{\prime}$ if
none of the vertices of $G_{i}$ is coloured by $\chi$.

We can correctly guess the colouring $\chi^{\prime}$ in at most $(q+1)^{w}$
time. We extend the colouring $\chi^{\prime}$ to $\chi$ as follows: we colour
an arbitrary vertex $v$ in $G_{i}$, if $v_{i}$ is coloured in $G^{\prime}$.
Otherwise, none of the vertices in $G_{i}$ is coloured. Now, some of the
vertices in $G$ are already dominated. For a subgraph $G_{j}$, if there exists
an edge $(v_{i},v_{j})\in E(G)$ and $\chi^{\prime}(v_{i})\neq c_{0}$, then
every vertex in $G_{j}$ is dominated by the presence of a coloured vertex in
$G_{i}$. Further, if $G_{i}$ contains a coloured vertex, all the vertices in
$G_{i}$ that are adjacent to this coloured vertex are dominated. Thus, a
vertex $v\in V(G_{i})$ is yet to be dominated if none of the neighbours of
$v_{i}$ (in the graph $G^{\prime}$) is coloured under $\chi^{\prime}$, or
equivalently the corresponding subgraphs in $G$ have no coloured vertex and
$v$ is not adjacent to the coloured vertex in $G_{i}$. In $\chi$, such
vertices in $G_{i}$ are dominated by colouring more vertices of $G_{i}$. Note
that a vertex in $G_{i}$ cannot be coloured using a colour already used in a
subgraph $G_{j}$ where $v_{j}\in N(N(v_{i}))$, in $G^{\prime}$. This gives us
a subset of admissible colours to use in $G_{i}$. Since, any pair of vertices
of $G_{i}$ has a common neighbour, colours cannot be repeated within $G_{i}$.
It follows that the set of coloured vertices in such a subgraph $G_{i}$
corresponds to a minimum dominating set of $G_{i}$. Thus the algorithm only
needs to check whether the size of the minimum dominating set of $G_{i}$
$\leq$ the number of admissible colours of $G_{i}$. It is easy to see that, in
a similar way, the minimum dominating set of $G$ can be computed starting from
the minimum dominating set of $G^{\prime}$, which in turn can be guessed in
$O(2^{w})$ time.

It follows that the $q$-Subset Square Colouring is FPT when parameterized by
modular width.

##  5 Bounds for $\chi_{ssc}$

In this section, we discuss bounds on the minimum number of colours needed for
subset square colouring some graph classes.

###  5.1 Trees

We show that $\chi_{ssc}(G)$ can be bounded by maximum degree, when $G$ is a
tree. We also show there exists a lower bound on $\chi_{ssc}(G)$ as a function
of $n$.

###### Lemma 41

Let $\Delta$ be the maximum degree of a tree, $T$. Then $\Delta$ colours are
sufficient to subset square colour the $T$. Moreover, $\Delta-1$ colours are
sometimes necessary.

###### Proof 27

Consider a tree $T$ rooted at a vertex $r$. Colour root $r$ with a colour
$c_{i}$ where $i\neq 0$. The nodes present in its next level are left
uncoloured. The nodes in following level (i.e., grandchildren of $r$) are
coloured using colours $c_{j}$ where $j\not\in\\{0,i\\}$ and each of the nodes
adjacent to each child of $r$ recieve a different colour. Such an assignment
is accomplished due to the fact that we have $\Delta-1$ colours after
colouring $r$ with $c_{i}$. This preserves the characteristic of subset square
colouring by assigning at most $\Delta$ unique colours to the vertices in the
closed neighbourhood of each node of $T$. In other words, we colour alternate
levels of a tree to subset square colour it. Therefore, either a vertex $v$ is
coloured or all its neighbours are coloured using at most $\Delta$ colours.

We remark that this may not be the optimal colouring in terms of number of
colours used. However, this serves as an upper bound on the number of colours
required to subset square colour a tree.

To prove the lower bound, consider a tree $T$ of height 2. Let $r$ be the root
and $d$ be the number of children of each vertex in $T$, except leaves.
Therefore, maximum degree $\Delta=d+1$. Let $v$ be a vertex at height 1. Note
that to subset square colour the children of $v$, we need $d$ colours if we
colour each child of $v$ using a different colour. Otherwise we have to colour
$v$ in order to dominate uncoloured child node(s) of $v$. By extending this
argument for each of $d-1$ siblings of $v$, any subset square colouring of $T$
uses $d$ colours. Thus the lower bound follows.

###### Corollary 42

There exist trees that require $\Omega(\sqrt{n})$ colours to be subset square
coloured.

Now, we know that Trees are a subclass of Bipartite graphs. Therefore the
lower bound applies to the class of Bipartite graphs too. In the next result,
we show a sub-class of Bipartite graphs can be subset square coloured using
constant number of colours.

###  5.2 Bipartite Permutation Graphs

In this section we discuss bounds on $\chi_{ssc}$ for bipartite permutation
graphs.
A graph is a bipartite permutation graph if it is both bipartite and
permutation graph. Let $G(A\uplus B,E)$ be a connected bipartite permutation
graph, then it admits the strong ordering, adjacency and enclosure properties,
as defined below [30].

  1. 1.

An ordering of the vertices $A$ in a bipartite graph $G(A\uplus B,E)$ has the
_adjacency property_ if for each vertex $v\in B$, the vertices in $N(v)$ are
consecutive in the ordering of $A$.

  2. 2.

An ordering of the vertices $A$ in a bipartite graph $G(A\uplus B,E)$ has the
_enclosure property_ if for every pair of vertices $v,u\in B$ such that $N(v)$
is a subset of $N(u)$, vertices in $N(u)-N(v)$ occur consecutively in the
ordering of $A$.

  3. 3.

_A strong ordering_ of the vertices of a bipartite graph $G(A\uplus B,E)$
consists of an ordering of $A$ and an ordering of $B$ such that for all
$(a,b^{\prime})$, $(a^{\prime},b)$ in $E$, where $a,a^{\prime}$ are in $A$ and
$b,b^{\prime}$ are in $B$, $a<a^{\prime}$ and $b<b^{\prime}$ imply $(a,b)$ and
$(a^{\prime},b^{\prime})$ are in $E$.

###### Lemma 43

If $G$ is a connected bipartite permutation graph then $\chi_{ssc}(G)\leq 4$.

Let $A=\\{a_{1},a_{2},\cdots a_{n}\\}$ and $B=\\{b_{1},b_{2},\cdots b_{m}\\}$
have the strong ordering property. For $a_{j}\in A$, let
$s(a_{j})=\min\\{i|b_{i}\in N(a_{j})\\}$ and $l(a_{j})=\max\\{i|b_{i}\in
N(a_{j})\\}$ be the smallest and largest vertex adjacent to $a_{j}$
respectively. (Symmetrically defined for $B$).

Now we colour a set of vertices from $A$, such that all vertices in $B$ are
dominated. In the first step, we colour the first vertex from $A$, $a_{1}$,
using colour one.

In the $k$th step we consider the smallest $j$ such that $b_{j}\in B$ is not
dominated. Then we colour $a_{i}\in A$ such that $i$ is the largest integer
such that $N(a_{i})$ contains $b_{j}$, using colour one, if $k$ is odd, or
otherwise, using colour two. Repeat this till every vertex in $B$ is
dominated. Now, if $a_{i},a_{j},a_{k}\in A$ are coloured in consecutive steps,
then $N(a_{i})$ and $N(a_{k})$ are disjoint. For contradiction, assume that
$N(a_{i})\cap N(a_{k})\neq\emptyset$. Let $j^{\prime}=l(a_{i})$. Then the
vertex $b_{j^{\prime}+1}$ is dominated by both $a_{j}$ and $a_{k}$. This
contradicts that $a_{j}$ was coloured by the algorithm to dominate
$b_{j^{\prime}+1}$. Thus no vertex in $B$ has repeating colours in its
neighborhood.

Similarly we can dominate all vertices in $A$ by colouring vertices in $B$
using colours three and four. This proves the result.

Further, we show that the class of Caterpillar graphs which is a subclass of
Bipartite Permutation graphs are $3$-subset square colourable.

###### Definition 11

[29] A _Caterpillar graph_ is a tree such that every vertex is at distance at
most one from a central path.

###### Lemma 44

If $G$ is a caterpillar graph then $\chi_{ssc}(G)=3$.

###### Proof 28

Let $P$ be the central path of $G$ with vertices $v_{1},v_{2},\dots
v_{n^{\prime}}$. Now colouring vertices in $P$ such that $v_{i}$, for $1\leq
i\leq n^{\prime}$, is given colour $(i\mod 3+1)$ is a valid $3$-subset square
colouring. Sometimes $3$ colours are necessary to subset square colour a
caterpillar graph. This can be seen by considering a caterpillar graph where
every vertex in the central path is adjacent to atleast three vertices of
degree one. The result follows.

###  5.3 Threshold graph

###### Definition 12

[23] A graph is a threshold graph if it can constructed from the empty graph
by repeatedly adding either an isolated vertex or a dominating vertex.

###### Lemma 45

If $G$ is a threshold graph then $\chi_{ssc}(G)=1$.

###### Proof 29

If isolated vertices are present, colour them using the same colour. By
colouring the last introduced dominating vertex $v$, we satisfy subset square
colouring $G$ as each vertex in $G$ has only one coloured vertex $v$ in its
closed neighbourhood.

We know that the family of threshold graphs lie in the intersection of split
graphs and cographs. We consider these graph classes in subsequent sections.

###  5.4 Split graph

###### Definition 13

[6] A graph $G$ is a split graph if $V(G)$ can be partitioned into two sets
$A$ and $B$ such that $A$ induces a clique and $B$ induces an independent set.

###### Theorem 46

There exist split graphs with $n$ vertices that require $\Omega(\sqrt{n})$
colours to be subset square coloured.

###### Proof 30

We will construct a split graph $G=(A\uplus B,E)$ as follows. Here $A$ induces
a clique and $B$ induces an independent set. Let $A=\\{v_{1},v_{2},\cdots
v_{n}\\}$ and $B=\\{v_{i,j}|1\leq i,j\leq n\\}$. Further we add edges from
$v_{i,j}\in B$ to $v_{i}\in A$ and $v_{j}\in A$, for all $1\leq i,j\leq n$.
Note that $G$ has $n^{2}+n$ vertices.

All vertices $v_{i,i}\in B$ are of degree $1$. To dominate $v_{i,i}\in B$,
either we need to colour $v_{i}$ or $v_{i,i}$, for all $1\leq i\leq n$. If
$v_{i}$ is coloured for all $i$, $1\leq i\leq n$, then we need $n$ colours
since all these vertices are adjacent to each other. Otherwise, assume there
exists an $i$ such that $v_{i}$ is not coloured and $v_{i,i}$ is coloured. Now
the $n-1$ vertices $v_{i,j}\in B$, where $i\neq j$ are dominated either by
themselves or by their other neighbour $v_{j}\in A$. Note that here every
vertex is dominated by a distinct vertex. Thus $O(n)$ vertices are coloured
from at least one of the sets, $\\{v_{i,j}|i\neq j\\}$ and $\\{v_{j}|j\neq
i\\}$. Since any two vertices from one of these sets are at distance at most
$2$, $O(n)$ colours are to be used.

###  5.5 Cographs

A graph with modular width two is a cograph [14]. From Lemma 39, the result
follows.

###### Lemma 47

If $G$ is a cograph, then $\chi_{ssc}(G)=2$.

## References

  * [1] Zachary Abel, Victor Alvarez, Erik D Demaine, Sándor P Fekete, Aman Gour, Adam Hesterberg, Phillip Keldenich, and Christian Scheffer.  Conflict-free colouring of graphs.  SIAM Journal on Discrete Mathematics, 32(4):2675–2702, 2018.
  * [2] V. P. Abidha, Pradeesha Ashok, Avi Tomar, and Dolly Yadav.  Coloring a dominating set without conflicts: q-subset square coloring.  In Computer Science – Theory and Applications, pages 17–34. Springer International Publishing, 2022.
  * [3] Pradeesha Ashok, Rathin Bhargava, Naman Gupta, Mohammad Khalid, and Dolly Yadav.  Structural parameterization for minimum conflict-free colouring.  In Discrete Applied Mathematics, Elsevier, 2022.
  * [4] Pradeesha Ashok and Rajath Rao and Avi Tomar.  Polynomial Kernels for Generalized Domination Problems.  In arXiv preprint arXiv:2211.03365, year 2022.
  * [5] D. W. Bange.  Efficient dominating sets in graphs.  Applications of Discrete Mathematics, page 189–199, 1988.
  * [6] Alan A Bertossi.  Dominating sets for split and bipartite graphs.  Information processing letters, 19(1):37–40, 1984.
  * [7] Hans L Bodlaender, Pal Gronass Drange, Markus S Dregi, Fedor V Fomin, Daniel Lokshtanov, and Michal Pilipczuk.  A c^kn 5-approximation algorithm for treewidth.  SIAM Journal on Computing, 45(2):317–378, 2016.
  * [8] Hans L Bodlaender, Bart MP Jansen, and Stefan Kratsch.  Kernelization lower bounds by cross-composition.  SIAM Journal on Discrete Mathematics, 28(1):277–305, 2014.
  * [9] Hans L Bodlaender and Ton Kloks.  Efficient and constructive algorithms for the pathwidth and treewidth of graphs.  Journal of Algorithms, 21(2):358–402, 1996.
  * [10] Hans L Bodlaender and Sudeshna Kolay and Astrid Pieterse.  Parameterized complexity of conflict-free graph coloring.  SIAM Journal on Discrete Mathematics, 35(3), 2003–2038, 2021.
  * [11] Yuehua Bu and Xubo Zhu.  An optimal square colouring of planar graphs.  Journal of combinatorial optimization, 24(4):580–592, 2012.
  * [12] Tiziana Calamoneri.  The l (h, k)-labelling problem: A survey and annotated bibliography.  The computer journal, 49(5):585–608, 2006.
  * [13] Gary Chartrand and Ping Zhang.  Chromatic graph theory.  Chapman and Hall/CRC, 2008.
  * [14] David Coudert, Guillaume Ducoffe, and Alexandru Popa.  Fully polynomial fpt algorithms for some classes of bounded clique-width graphs.  ACM Transactions on Algorithms (TALG), 15(3):1–57, 2019.
  * [15] Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.  Parameterized algorithms, volume 5.  Springer, 2015.
  * [16] Rodney G Downey, Michael R Fellows, and Ulrike Stege.  Parameterized complexity: A framework for systematically confronting computational intractability.  In Contemporary trends in discrete mathematics: From DIMACS and DIMATIA to the future, volume 49, pages 49–99, 1999.
  * [17] Lawrence H Erickson and Steven M LaValle.  An art gallery approach to ensuring that landmarks are distinguishable.  In Robotics: science and systems, volume 7, pages 81–88, 2012.
  * [18] Jiří Fiala, Petr A Golovach, and Jan Kratochvíl.  Parameterized complexity of colouring problems: Treewidth versus vertex cover.  Theoretical Computer Science, 412(23):2513–2523, 2011.
  * [19] Jakub Gajarský, Michael Lampis, and Sebastian Ordyniak.  Parameterized algorithms for modular-width.  In Gregory Gutin and Stefan Szeider, editors, Parameterized and Exact Computation, pages 163–176, Cham, 2013. Springer International Publishing.
  * [20] Robert Ganian.  Improving vertex cover as a graph parameter.  Discrete Mathematics & Theoretical Computer Science, 17, 2015.
  * [21] M. R. Garey and D. S. Johnson.  Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences).  W. H. Freeman, first edition edition, 1979.
  * [22] Luisa Gargano and Adele A. Rescigno.  Complexity of conflict-free colourings of graphs.  Theoretical Computer Science, 566:39–49, 2015.
  * [23] Martin Charles Golumbic.  Algorithmic graph theory and perfect graphs.  Elsevier.  2004\.
  * [24] Jerrold Griggs and Roger Yeh.  Labelling graphs with a condition at distance 2.  SIAM J. Discrete Math., 5:586–595, 11 1992.
  * [25] Jan van den Heuvel and Sean McGuinness.  Coloring the square of a planar graph.  Journal of Graph Theory, 42(2):110–124, 2003.
  * [26] John E Hopcroft and Mukkai S Krishnamoorthy.  On the harmonious coloring of graphs.  SIAM Journal on Algebraic Discrete Methods, 4(3):306–311, 1983\.
  * [27] Daniel Lokshtanov, Neeldhara Misra, Geevarghese Philip, MS Ramanujan, and Saket Saurabh.  Hardness of r-dominating set on graphs of diameter (r+ 1).  In International Symposium on Parameterized and Exact Computation, pages 255–267. Springer, 2013.
  * [28] Gary MacGillivray and Karen Seyffarth.  Domination numbers of planar graphs.  Journal of Graph Theory, 22(3):213–229, 1996.
  * [29] Carmen Ortiz and Mónica Villanueva.  Maximal independent sets in caterpillar graphs.  Discrete applied mathematics, 160(3):259–266, 2012.
  * [30] Jeremy Spinrad, Andreas Brandstädt, and Lorna Stewart.  Bipartite permutation graphs.  Discrete Applied Mathematics, 18(3):279–292, 1987.
  * [31] Yue-Li Wang, Tsong-Wuu Lin, and Lin-Yuan Wang.  The local harmonious chromatic problem.  In Proceedings of the 27th Workshop on Combinatorial Mathematics and Computation Theory, Taichung, Taiwan, volume 30. Citeseer, 2010.