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 classic graph coloring problem. Majumdar et. al. [CALDAM 2017] studied this problem and showed that the decision version of the $(k, i)$-coloring problem is fixed parameter tractable (FPT) with tree-width as the parameter. They asked if there exists an FPT algorithm with the size of the feedback vertex set (FVS) as the parameter without using tree-width machinery. We answer this in positive by giving a parameterized algorithm with the size of the FVS as the parameter. We also give a faster and simpler exact algorithm for $(k,k-1)$-coloring, and make progress on the NP-completeness of specific cases of (k,i)-coloring.
Saurabh Joshi
Principal Researcher
My research interests include Blockchain, Distributed Systems, Constraint Programming, Formal Verification, Programming Languages and Program Analysis.