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?

1 Answer

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.

• 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$). – Mohammad Al-Turkistany Apr 6 '17 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. – Emil Jeřábek Apr 6 '17 at 12:42
• @MohammadAl-Turkistany : It makes no difference and the same idea works even for 3-connected planar graphs. Insert a new vertex into each face and join it to each vertex of the face. Colour all the new vertices with the same colour. – Brendan McKay Apr 6 '17 at 12:44
• @EmilJeřábek So, If we color some of the edges of a bridgeless planar cubic graph then the extendibility problem is NP-complete. Do you see a simple reduction in terms of 3-edge colorability? – Mohammad Al-Turkistany Apr 6 '17 at 12:51