TY - JOUR

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

AU - Khuller, Samir

AU - Vazirani, Vijay V.

N1 - Funding Information:
* Research done in part while this author was supported by an IBM Graduate Fellowship at Cornell University. * * Supported in part by NSF grant DCR 85-52938 and PYI matching funds from AT&T Bell Labs and Sun Microsystems, Inc. at Cornell University.

PY - 1991/9/30

Y1 - 1991/9/30

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0026222329&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026222329&partnerID=8YFLogxK

U2 - 10.1016/0304-3975(91)90081-C

DO - 10.1016/0304-3975(91)90081-C

M3 - Article

AN - SCOPUS:0026222329

VL - 88

SP - 183

EP - 189

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 1

ER -