2
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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$). $\endgroup$
    – Mohammad Al-Turkistany
    Commented Apr 6, 2017 at 12:36
  • $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Commented Apr 6, 2017 at 12:42
  • 2
    $\begingroup$ @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. $\endgroup$
    – Brendan McKay
    Commented Apr 6, 2017 at 12:44
  • $\begingroup$ @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? $\endgroup$
    – Mohammad Al-Turkistany
    Commented Apr 6, 2017 at 12:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .