In this paper, we consider the problem Defective Coloring. Given a graph G and two positive integers k and \(\Delta ^\) , the objective is to determine whether it is possible to obtain a coloring (not necessarily proper) of the vertices of G using at most k colors such that each vertex in a color class c has at most \(\Delta ^\) neighbors in the same color class. Defective Coloring is a generalization of Graph Coloring with \(\Delta ^=0\) . The optimization variant of this problem, which aims to find the minimum number of colors k, is known to be NP-hard even for split graphs and cographs. Belmonte, Lampis, and Mitsou (SIDMA 2020) showed that Defective Coloring is W[1]-hard when parameterized by tree-width, path-width, tree-depth, or feedback vertex set. The problem is W[1]-hard parameterized by modular-width or clique-width as Defective Coloring is NP-hard on cographs. They asked as an open question whether Defective Coloring is fixed-parameter tractable ( \(\texttt {FPT}\) ) when parameterized by modular-width, clique-width or neighborhood diversity combined with either k or \(\Delta ^\) . In an effort to address the question concerning modular-width, this study investigates the parameters neighborhood diversity and twin-cover, which are special cases of modular-width. We show that Defective Coloring is \(\texttt {FPT}\) when parameterized by twin-cover, distance to disjoint paths, or the combined parameters neighborhood diversity and k. The latter result implies an FPT algorithm for complete-d-partite graphs, a subclass of cographs, parameterized by d. This provides a partial response to an open question raised in the above paper. We present an algorithm for graphs with bounded distance to d-degree and as a corollary we obtain an FPTalgorithm parameterized by distance to disjoint paths. Furthermore, the study also presents a 1-additive approximation algorithm for split graphs.

On the Structural Parameterized Complexity of Defective Coloring

会议论文
发表日期：

2025年

查看全文

Sriram Bhyravarapu,
Pankaj Kumar,
Saket Saurabh

摘要

In this paper, we consider the problem Defective Coloring. Given a graph G and two positive integers k and \(\Delta ^*\) , the objective is to determine whether it is possible to obtain a coloring (not necessarily proper) of the vertices of G using at most k colors such that each vertex in a color class c has at most \(\Delta ^*\) neighbors in the same color class. Defective Coloring is a generalization of Graph Coloring with \(\Delta ^*=0\) . The optimization variant of this problem, which aims to find the minimum number of colors k, is known to be NP-hard even for split graphs and cographs. Belmonte, Lampis, and Mitsou (SIDMA 2020) showed that Defective Coloring is W[1]-hard when parameterized by tree-width, path-width, tree-depth, or feedback vertex set. The problem is W[1]-hard parameterized by modular-width or clique-width as Defective Coloring is NP-hard on cographs. They asked as an open question whether Defective Coloring is fixed-parameter tractable ( \(\texttt {FPT}\) ) when parameterized by modular-width, clique-width or neighborhood diversity combined with either k or \(\Delta ^*\) . In an effort to address the question concerning modular-width, this study investigates the parameters neighborhood diversity and twin-cover, which are special cases of modular-width. We show that Defective Coloring is \(\texttt {FPT}\) when parameterized by twin-cover, distance to disjoint paths, or the combined parameters neighborhood diversity and k. The latter result implies an FPT algorithm for complete-d-partite graphs, a subclass of cographs, parameterized by d. This provides a partial response to an open question raised in the above paper. We present an algorithm for graphs with bounded distance to d-degree and as a corollary we obtain an FPTalgorithm parameterized by distance to disjoint paths. Furthermore, the study also presents a 1-additive approximation algorithm for split graphs.