Joshi, Saurabh and Kalyanasundaram, Subrahmanyam and Kare, A S and Bhyravarapu, Sriram
(2018)
On the Tractability of (k, i)-Coloring.
In:
Algorithms and Discrete Applied Mathematics.
Theoretical Computer Science and General Issues, 10743
.
Springer, pp. 188-198.
ISBN 9783319741802
Abstract
In an undirected graph, a proper (
k, i
)-coloring is an assign-
ment of a set of
k
colors to each vertex such that any two adjacent
vertices have at most
i
common colors. The (
k, i
)-coloring problem is
to compute the minimum number of colors required for a proper
(
k, i
)-
coloring. This is a generalization of the classic graph colo
ring problem.
Majumdar et. al. [CALDAM 2017] studied this problem and show
ed
that the decision version of the (
k, i
)-coloring problem is fixed parameter
tractable (FPT) with tree-width as the parameter. They aske
d if there
exists an FPT algorithm with the size of the feedback vertex s
et (FVS)
as the parameter without using tree-width machinery. We ans
wer this in
positive by giving a parameterized algorithm with the size o
f the FVS
as the parameter. We also give a faster and simpler exact algo
rithm for
(
k, k
−
1)-coloring, and make progress on the NP-completeness of sp
ecific
cases of (
k, i
)-coloring
Actions (login required)
 |
View Item |
Altmetric
Altmetric