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

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.
9 pages, appears in part in an ICTCS 2001 paper by the same authors, minor revision of the above

Keywords

Computational Complexity, F.1.3; F.2.2

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/99663

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0106045
 http://arxiv.org/abs/cs/0106045

Collections

arXiv