On the Tractability of $(k,i)$-Coloring

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.

Publication
Proceedings of the 4th International Conference on Algorithms and Discrete Applied Mathematics - CALDAM 2018, Guwahati, India
Date