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

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

2001-06-21

arxiv.org/abs/cs/0106045v2

Computer Science

Computational Complexity

9 pages, appears in part in an ICTCS 2001 paper by the same authors, minor revision of the above

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

A Note on the Complexity of Computing the Smallest Four-Coloring of Planar Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Note on the Complexity of Computing the Smallest Four-Coloring of Planar Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Note on the Complexity of Computing the Smallest Four-Coloring of Planar Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-42244