Oriented coloring in planar, bipartite, bounded degree 3 acyclic oriented graphs

An oriented k-coloring of an oriented graph is a partition of V into k subsets such that there are no two adjacent vertices belonging to the same subset, and all the arcs between a pair of subsets have the same orientation. The decision problem k-oriented chromatic number (ocnk) consists of an oriented graph and an integer k>0, plus the question if there exists an oriented k-coloring of . We present a proof that ocn4 is NP-complete for an acyclic oriented graph such that the underlying graph has maximum degree 3 and it is at the same time connected, planar and bipartite. Our result is optimum, since ocn3 is in P, and ocnk is also in P when the underlying graph has maximum degree 2.