@article {15204,
	title = {Planar graph coloring is not self-reducible, assuming P /= NP},
	journal = {Theoretical Computer Science},
	volume = {88},
	year = {1991},
	month = {1991/09/30/},
	pages = {183 - 189},
	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.},
	isbn = {0304-3975},
	doi = {10.1016/0304-3975(91)90081-C},
	url = {http://www.sciencedirect.com/science/article/pii/030439759190081C},
	author = {Khuller, Samir and Vazirani,Vijay V.}
}
