On the tractability of (k,i)-coloring

Bhyravarapu, Sriram and Joshi, Saurabh and Kalyanasundaram, Subrahmanyam and et al, . (2021) On the tractability of (k,i)-coloring. Discrete Applied Mathematics, 305. pp. 329-339. ISSN 0166-218X

Full text not available from this repository. (Request a copy)


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 tree-width 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 NP-complete for any fixed values i,k, whenever i<k, thereby settling a conjecture of Méndez-Díaz and Zabala (1999) and again asked by Majumdar, Neogi, Raman and Tale. The NP-completeness result improves the partial NP-completeness shown in the preliminary version of this paper published in CALDAM 2018. © 2020 Elsevier B.V.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Kalyanasundaram, SubrahmanyamUNSPECIFIED
Item Type: Article
Additional Information: This work is partially supported by ECR/2017/001126 grant from SERB, DST, India . The authors would like to thank the anonymous reviewer for helpful comments, and pointing out a flaw in the proof of Theorem 12 in an earlier version of the paper.
Uncontrolled Keywords: Graph Coloring; NP-Completeness; Parameterized Algorithms
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: . LibTrainee 2021
Date Deposited: 12 Sep 2022 08:54
Last Modified: 12 Sep 2022 08:54
URI: http://raiith.iith.ac.in/id/eprint/10540
Publisher URL: http://doi.org/10.1016/j.dam.2020.08.018
OA policy: https://v2.sherpa.ac.uk/id/publication/11425
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 10540 Statistics for this ePrint Item