PARAMETERIZED PRE-COLORING EXTENSION AND LIST COLORING PROBLEMS

Golovach, Paulusma, and Song [Inform. and Comput., 237 (2014), pp. 204-214] asked to determine the parameterized complexity of the following problems parameterized by k: 1. Given a graph G, a clique modulator D (a clique modulator is a set of vertices, whose removal results in a clique) of size k for G, and a list L(v) of colors for every v is an element of V (G), decide whether G has a proper list coloring. 2. Given a graph G, a clique modulator D of size k for G, and a pre-coloring \lambda P : X \rightarrow Q for X \subseteq V (G), decide whether \lambda P can be extended to a proper coloring of G using only colors from Q. For problem 1 we design an \scrO \ast (2k)- time randomized algorithm and for problem 2 we obtain a kernel with at most 3k vertices. Banik et al. [in Proceedings of IWOCA 2019, Springer, Berlin, 2019, pp. 61-69] proved the following problem is fixed-parameter tractable and asked whether it admits a polynomial kernel: Given a graph G, an integer k, and a list L(v) of exactly n k colors for every v \in V (G), decide whether there is a proper list coloring for G. We obtain a kernel with \scrO (k2) vertices and colors and a compression to a variation of the problem with \scrO (k) vertices and \scrO (k2) colors.