On the proper orientation number of bipartite graphs

An orientation of a graph G is a digraph D obtained from G   by replacing each edge by exactly one of the two possible arcs with the same endvertices. For each v∈V(G)v∈V(G), the indegree of v in D  , denoted by dD−(v), is the number of arcs with head v in D. An orientation D of G is proper   if dD−(u)≠dD−(v), for all uv∈E(G)uv∈E(G). The proper orientation number of a graph G  , denoted by χ→(G), is the minimum of the maximum indegree over all its proper orientations. In this paper, we prove that χ→(G)≤(Δ(G)+Δ(G))/2+1 if G   is a bipartite graph, and χ→(G)≤4 if G   is a tree. It is well-known that χ→(G)≤Δ(G), for every graph G  . However, we prove that deciding whether χ→(G)≤Δ(G)−1 is already an NPNP-complete problem on graphs with Δ(G)=kΔ(G)=k, for every k≥3k≥3. We also show that it is NPNP-complete to decide whether χ→(G)≤2, for planar subcubic graphs G  . Moreover, we prove that it is NPNP-complete to decide whether χ→(G)≤3, for planar bipartite graphs G with maximum degree 5.