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

Our result defines a P versus NP-complete dichotomy with respect to the maximum degree Δ(G): OCNk is polynomial if Δ(G)<3 and NP-complete if Δ(G)≥3, since it is known that OCN3 is in P, and that OCNk is in P when the underlying graph has Δ(G)≤2.