|
EPrints@IIT Delhi >
Faculty Research Publicatons >
Computer Science and Engineering >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/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 |
Size | Format |
|---|
| khullerpla91.pdf | | 147Kb | Adobe PDF | View/Open |
|
Show full item record
All items in DSpace are protected by copyright, with all rights reserved.
|
