# Is 4-colors precoloring extension for planar graphs fixed parameter tractable?

Given a planar graph $G=(V,E)$, there exists a quadratic algorithms for 4-coloring $G$ (and $G$ is surely 4-colorable).

Assume you are given a set of $k$ constraints of the form "$v_i \text{ is colored by }f(v_i)$".

Our goal is to determine whether this precoloring could be extended into a valid 4-coloring of $G$.

Can the 4-colors precoloring extension of $G$ be solved in FPT time (with respect to $k$)?

Notice that the problem is NP-hard by a reduction from 3-coloring of planar graphs - Given a planar instance $G$ which we want to check for 3-colorability, create a vertex $v'$ for each vertex $v$, connect $v'$ with $v$, and force all of the new vertices to be colored in the 4th color.

• You are asking for containment in FPT. Do you know whether your problem is contained in XP? – Gamow Feb 13 '15 at 13:27