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.

  • 4
    $\begingroup$ You are asking for containment in FPT. Do you know whether your problem is contained in XP? $\endgroup$
    – Gamow
    Commented Feb 13, 2015 at 13:27


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.