Complexity of 4-coloring a map with constraints

Question

The well-known Four color theorem states that every map which is divided into regions, can be colored using 4 colors such that no two adjacent regions have the same color.

In fact, there exists a quadratic algorithm for 4-coloring planar graphs.

Suppose you are given a map (e.g. the world's map) and a list of $k$ constraints, e.g. Greece is colored blue, and Spain, Italy and Uruguay are red.

Can this problem be solved in poly time if $k$ is part of the input?

Can this be solved in poly time if $k$ is fixed (i.e. is the problem fixed parameter tractable with respect to $k$)?

Answer 1

It is $NP$-complete. Consider a graph $G$ which is modified by duplicating every vertex, and connecting every duplicate vertex to its original. Then if we constrain all the duplicate vertices to a fixed color, then the thus obtained graph is 4-colorable (with constraints) if and only if the original graph is 3-colorable.

Answer 2

To add to the other answer, the name of the problem you are interested in is precoloring extension: given a graph $G$ with some precolored vertices and a color bound $\ell$, can the precoloring of $G$ be extended to a proper coloring of all vertices of $G$ using not more than $\ell$ colors? This problem is NP-complete for planar bipartite graphs with fixed $\ell = 3$ as shown by Kratochvíl [1].

The problem has also been investigated in a parameterized setting, for instance, when either the number of precolored vertices or the number of colors used in the precoloring is restricted to be at most $k$. Both cases are W[1]-hard, see e.g. [2].

---

[1] Kratochvíl, Jan. "Precoloring extension with fixed color bound." Acta Math. Univ. Comen 62 (1993): 139-153.

[2] Marx, Dániel. "Parameterized coloring problems on chordal graphs." Theoretical Computer Science 351.3 (2006): 407-424.