EPrints@IIT Delhi >
Faculty Research Publicatons  >
Computer Science and Engineering >

Please use this identifier to cite or link to this item: http://eprint.iitd.ac.in/handle/2074/2507

Title: Planar graph coloring is not self-reducible, assuming P ≠ NP
Authors: Vazirani, Vijay V
Khuller, Samir
Keywords: Lexicographically
Planar graph
Four coloring
Issue Date: 1991
Citation: Theoretical Computer Science, 88(1), 183-189p.
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 k4.
URI: http://eprint.iitd.ac.in/dspace/handle/2074/2507
Appears in Collections:Computer Science and Engineering

Files in This Item:

File Description SizeFormat
khullerpla91.pdf147.05 kBAdobe PDFView/Open
View Statistics

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! DSpace Software Copyright © 2002-2010  Duraspace - Feedback