  We consider the Functional Orientation 2-Color problem, which was introduced
by Valiant in his seminal paper on holographic algorithms [SIAM J. Comput.,
37(5), 2008]. For this decision problem, Valiant gave a polynomial time
holographic algorithm for planar graphs of maximum degree 3, and showed that
the problem is NP-complete for planar graphs of maximum degree 10. A recent
result on defective graph coloring by Corr\^ea et al. [Australas. J. Combin.,
43, 2009] implies that the problem is already hard for planar graphs of maximum
degree 8. Together, these results leave open the hardness question for graphs
of maximum degree between 4 and 7. We close this gap by showing that the answer
is always yes for arbitrary graphs of maximum degree 5, and that the problem is
NP-complete for planar graphs of maximum degree 6. Moreover, for graphs of
maximum degree 5, we note that a linear time algorithm for finding a solution
exists.
