Planar graph coloring is not self-reducible, assuming P ≠ NP

Samir Khuller*, Vijay V. Vazirani

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

We show that obtaining the lexicographically first four coloring of a planar graph is NP-hard. This shows that planar graph four-coloring is not self-reducible, assuming P≠ NP. One consequence of our result is that the schema of Jerrum et al. (1986) cannot be used for approximately counting the number of four colorings of a planar graph. These results extend to planar graph k-coloring, for k≥4.

Original languageEnglish (US)
Pages (from-to)183-189
Number of pages7
JournalTheoretical Computer Science
Volume88
Issue number1
DOIs
StatePublished - Sep 30 1991

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Planar graph coloring is not self-reducible, assuming P ≠ NP'. Together they form a unique fingerprint.

Cite this