  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. We show 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 and
simpler 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 Mendez-Diaz 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.
