2
$\begingroup$

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?

$\endgroup$
  • 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 at 9:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.