# Complexity of a variant of Four coloring theorem

The Four color theorem states that every planar graph can be properly colored by four colors. An equivalent statement is that every bridgeless planar cubic graph is 3-edge colorable. Therefore, 4-coloring planar graphs is decidable in polynomial-time.

Now let us assume that we are given the colors of some vertices (possibly non-adjacent), Is it easy to complete it to proper 4-coloring?

Four Coloring extendibility

INPUT: planar graph and a subset of nodes, each node assigned some color

OUTPUT Is the coloring extendable to a proper 4-coloring?

I suspect that it is computationally hard to decide the existence of such coloring.

How hard is it to decide the extendibility of partial 4-coloring of planar graphs? Is it polynomial solvable or is it NP-complete?

• Nice, while this answer the question but planar graphs with leafs are not interesting. Is it still NP-complete for planar graphs with minimum node degree $k$ ( $k \ge 2$). Apr 6, 2017 at 12:36
• Note that any planar graph has minimal degree at most $5$, hence you must have $k\le 5$ if the question is to be nontrivial. Then the problem is still NP-complete: instead of a single node, attach to each node a copy of a fixed gadget of minimal degree $k$ (that is, attach the original node to one node of the gadget), with colours assigned to the gadgets in such a way that the neighbour of the original node has the one fixed colour. Apr 6, 2017 at 12:42