On the proper orientation number of bipartite graphs

Description

An {\it orientation} of a graph $G$ is a digraph $D$ obtained from $G$ by replacing each edge by exactly one of the twopossible arcs with the same endvertices.For each $v \in V(G)$, the \emph{indegree} of $v$ in $D$, denoted by $d^-_D(v)$, is the number of arcs with head $v$ in $D$.An orientation $D$ of $G$ is \emph{proper} if $d^-_D(u)\neq d^-_D(v)$, for all $uv\in E(G)$.The \emph{proper orientation number} of a graph $G$, denoted by $po(G)$, is the minimum of the maximumindegree over all its proper orientations. In this paper, we prove that $po(G) \leq \left(\Delta(G) + \sqrt{\Delta(G)}\right)/2 + 1$ if $G$ is a bipartite graph, and $po(G)\leq 4$ if $G$ is a tree.% Moreover, we show that deciding whether the proper orientation number is at most~2 and at most~3 % is an $NP$-complete problem for planar subcubic graphs and planar bipartite graphs, respectively. It is well-known that $po(G)\leq \Delta(G)$, for every graph $G$.However, we prove that deciding whether $po(G)\leq \Delta(G)-1$ is already an $NP$-complete problem on graphs with $\Delta(G) = k$, for every $k \geq 3$.We also show that it is $NP$-complete to decide whether $po(G)\leq 2$, for planar \emph{subcubic} graphs $G$. Moreover, we prove that it is $NP$-complete to decide whether $po(G)\leq 3$, for planar bipartite graphs $G$ with maximum degree 5.

Abstract

International audience

Additional details