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?

  • 3
    $\begingroup$ 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. $\endgroup$
    – Gamow
    Jun 24, 2019 at 9:12


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.