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

Simple item page
dc.creatorGrosse, Andre
dc.creatorRothe, Joerg
dc.creatorWechsung, Gerd
dc.date2001-06-21
dc.date2006-02-07
dc.date.accessioned2026-07-07T06:34:54Z
dc.date.available2026-07-07T06:34:54Z
dc.descriptionWe 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.
dc.description9 pages, appears in part in an ICTCS 2001 paper by the same authors, minor revision of the above
dc.identifierhttps://arxiv.org/abs/cs/0106045
dc.identifierhttp://arxiv.org/abs/cs/0106045
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/99663
dc.subjectComputational Complexity
dc.subjectF.1.3; F.2.2
dc.titleA Note on the Complexity of Computing the Smallest Four-Coloring of Planar Graphs
dc.typetext

Files

Collections

arXiv