1
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.