The complexity of the proper orientation number

•We study the computational complexity of the proper orientation number.•We show that, it is NP-complete to decide whether χ→(G)=2, for a given planar graph G.•Also, we prove that there is a polynomial time algorithm for determining the proper orientation number of 3-regular graphs. In sharp contrast, we will prove that this problem is NP-hard for 4-regular graphs.

A proper orientation of a graph G=(V,E)G=(V,E) is an orientation D   of E(G)E(G) such that for every two adjacent vertices v and u  , dD−(v)≠dD−(u) where dD−(v) is the number of edges with head v in D. The proper orientation number of G   is defined as χ→(G)=minD∈Γmaxv∈V(G)dD−(v) where Γ is the set of proper orientations of G  . We have χ(G)−1⩽χ→(G)⩽Δ(G), where χ(G)χ(G) and Δ(G)Δ(G) denote the chromatic number and the maximum degree of G, respectively. We show that, it is NP-complete to decide whether χ→(G)=2, for a given planar graph G. Also, we prove that there is a polynomial time algorithm for determining the proper orientation number of 3-regular graphs. In sharp contrast, we will prove that this problem is NP-hard for 4-regular graphs.