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?