2
$\begingroup$

Is there a polynomial time and polynomial space quantum algorithm for finding a 4 colouring of any loopless planar graph?

$\endgroup$
7
$\begingroup$

There is evidently a classical polynomial-time algorithm for finding a four-coloring of a given planar graph, so the answer to the question is "yes" for the trivial reason that every polynomial-time classical algorithm can be implemented as a polynomial-time quantum algorithm. (Also, polynomial time implies polynomial space, for both quantum and classical algorithms, so that part is trivially satisfied.)

An important aspect of the problem that the question describes is that we are asked to find a four-coloring, as opposed to deciding whether or not a four-coloring exists. Deciding the existence of a four-coloring for a planar graph would be trivial: the correct answer is always "yes" by the four-color theorem. This theorem was proved in 1976 by Appel and Haken's famous computer-assisted proof, and it is my understanding that Appel and Haken's proof can in principle be turned into a quartic-time algorithm for finding a four-coloring of a planar graph.

The proof of the four-color theorem was simplified somewhat in this paper:

Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas. The four-colour theorem. Journal of Combinatorial Theory, Series B 70: 2-44, 1997.

(Available from CiteSeerX.)

In this paper, the authors claim explicitly (see Section 6) that their proof yields a quadratic-time classical algorithm for finding a four-coloring of a planar graph.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.