The hardness of the functional orientation 2-color problem (Q2848741)

A functional orientation of a graph is a function \(f\) from the vertex set to itself such that each vertex \(u\) is adjacent to \(v = f(u)\). The name arises from assigning a direction on the edge \(uv\): each vertex then has exactly one edge directed outwards. Functional orientations occur in applications such as finite-state machines, the analysis of algorithms, and hash functions.NEWLINENEWLINEThe functional orientation 2-color problem is to determine when a graph has a vertex 2-coloring and a functional orientation \(f\) such that any edge \(uv\) joining two vertices of the same color has either \(f(u) = v\) or \(f(v) = u\). This problem is known to be NP-complete for planar graphs of maximum degree at least ten, but is polynomial-time solvable for planar graphs of maximum degree three.NEWLINENEWLINEThe authors show that this problem is solvable in linear time for planar graphs of maximum degree five and is NP-complete for planar graphs of maximum degree six.