7
$\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.

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

Your Answer

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

Browse other questions tagged or ask your own question.