Complexity of 4-coloring a map with constraints 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$)?
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.