A Note on the Complexity of Computing the Smallest Four-Coloring of Planar Graphs
Andre Grosse, Joerg Rothe, Gerd Wechsung
2006
We email you when a new notice or a question about this paper appears.
Abstract
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 this problem to be NP-hard, and conclude that it is not self-reducible in the sense of Schnorr, assuming P \neq NP. We discuss this application to non-self-reducibility and provide a general related result.
Abstract licence: CC0
Reads
Read by people on this page
None yet.
Checked or read by AI through naulon
None yet.
A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.
Are you an author?
Is this your paper?
Claim it to add your note and be paid when agents cite it. Free.