The Hardness of the Functional Orientation 2-Color Problem

The authors consider the Functional Orientation 2-Color problem, which was introduced by Valiant in his seminal paper on holographic algorithms. For this decision problem, Valiant gave a polynomial time algorithm for planar graphs of maximum degree 3, and showed that the problem is NP-complete for planar graphs of maximum degree 10. They close this gap by showing that the answer is always yes for maximum degree 5, and that the problem is NP-complete for planar graphs of maximum degree 6. Moreover, for graphs of maximum degree 5, they note that a linear time algorithm for finding a solution exists.