# “Planar graph coloring is not self-reducible” is this about all $p$-relations encoding that problem?

I have a question about the paper "Planar graph coloring is not self-reducible" by Samir Khuller and Vijay Vazirani.

The final theorem in that paper states that "Planar Graph k-coloring is not self reducible, assuming NP!=P." In reading the proof of this (with $$k =4$$), it seems they actually prove a statement about a particular way to encode $$(\text{Plane graph }G,\text{proper } 4\text{-coloring of }G)$$ as a $$p$$-relation. In particular it's crucial to the reduction (Theorem 3.1) that the encoding is one where the vertices of the graph are given an ordering, and colorings are stored as a string of letters, with each letter describing the color of the $$i$$th vertex. I can imagine that most reasonable encodings look this way, but maybe there are some that don't.

Questions: Is there a way to interpret their theorem as proving that all encodings of the plane graph $$4$$-coloring problem as a $$p$$-relation are not self-reducible (assuming $$P \not = NP$$)? Is there a way to formalize the class of $$p$$-relations that they prove are not self-reducible? Maybe I'm misunderstanding something?

• You may want to read "On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P" by Große, Rothe and Wechsung, Information Processing Letters 99 (2006) 215–221. They put the Khuller & Vazirani result into a much broader context. – Gamow Jun 24 at 9:12