On the Tractability of (k, i)-Coloring

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

1802.03634.pdf - Accepted Version

Download (176kB) | Preview


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

[error in script]
IITH Creators:
IITH CreatorsORCiD
Item Type: Book Section
Uncontrolled Keywords: Computer Science Theoretical Computer Science
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: Team Library
Date Deposited: 12 Mar 2018 05:01
Last Modified: 25 Apr 2018 04:29
URI: http://raiith.iith.ac.in/id/eprint/3821
Publisher URL: https://doi.org/10.1007/978-3-319-74180-2_16
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 3821 Statistics for this ePrint Item