8
$\begingroup$

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.

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

0

Reset to default

Your Answer

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