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$)?