A Note on the Complexity of Computing the Smallest Four-Coloring of Planar Graphs

Andre Grosse, Joerg Rothe, Gerd Wechsung

We show that computing the lexicographically first four-coloring for planar graphs is P^{NP}-hard. This result optimally improves upon a result of Khuller and Vazirani who prove th…