Bhyravarapu, Sriram and Joshi, Saurabh and Kalyanasundaram, Subrahmanyam and et al, .
(2021)
On the tractability of (k,i)coloring.
Discrete Applied Mathematics, 305.
pp. 329339.
ISSN 0166218X
Full text not available from this repository.
(
Request a copy)
Abstract
In an undirected graph, a proper (k,i)coloring is an assignment 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 classical graph coloring problem. We design a parameterized algorithm for the (k,i)coloring problem with the size of the feedback vertex set as a parameter. Our algorithm does not use treewidth machinery, thus answering a question of Majumdar, Neogi, Raman and Tale [CALDAM 2017]. We also give a faster exact algorithm for (k,k−1)coloring. From the hardness perspective, we show that the (k,i)coloring problem is NPcomplete for any fixed values i,k, whenever i<k, thereby settling a conjecture of MéndezDíaz and Zabala (1999) and again asked by Majumdar, Neogi, Raman and Tale. The NPcompleteness result improves the partial NPcompleteness shown in the preliminary version of this paper published in CALDAM 2018. © 2020 Elsevier B.V.
[error in script]
Actions (login required)

View Item 