Search

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

Abstract: In this article we provide hardness results and approximation algorithms for the following three natural degree-constrained subgraph problems, which take as input an undirected graph . Let be a fixed integer. The () problem takes as additional input a weight function , and asks for a subset such that the subgraph induced by is connected, has maximum degree at most , and is maximized. The Minimum Subgraph of Minimum Degree () problem involves finding a smallest subgraph of with minimum degree at least . Finally, the Dual Degree-dense -Subgraph () problem consists in finding a subgraph of such that and the minimum degree in is maximized. [Copyright &y& Elsevier]