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. 188198.
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 treewidth 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 treewidth 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 NPcompleteness of sp
ecific
cases of (
k, i
)coloring
[error in script]
Actions (login required)

View Item 