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?