Options
On the complexity of minimum q-domination partization problems
Date Issued
01-03-2022
Author(s)
Das, Sayani
Indian Institute of Technology, Madras
Abstract
A domination coloring of a graph G is a proper vertex coloring with an additional condition that each vertex dominates a color class and each color class is dominated by a vertex. The minimum number of colors used in a domination coloring of G is denoted as χdd(G) and it is called domination chromatic number of G. In this paper, we give a polynomial-time characterization of graphs with domination chromatic number at most 3 and consider the approximability of a node deletion problem called minimum q-domination partization. Given a graph G, in the Minimumq-Domination Partization problem (in short Min-q-Domination-Partization), the objective is to find a vertex set S of minimum size such that χdd(G[V\ S]) ≤ q. For q= 2 , we prove that it is APX-complete and is best approximable within a factor of 2. For q= 3 , it is approximable within a factor of O(logn) and it is equivalent to minimum odd cycle transversal problem.
Volume
43