The [Four color theorem](https://en.wikipedia.org/wiki/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?
> 
> 
> 



Complexity of a variant of Four coloring theorem
The problem is NP-complete. Here is a reduction from 3-colorability of planar graphs: take the input graph, attach to each node a new node, and assign one fixed color to all the new nodes.


