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 two possible 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 maximum indegree over all its proper orientations. In this paper, we prove that~$\po(G) \leq \left\lfloor \left(\Delta(G) + \sqrt{\Delta(G)}\right)/2 \right\rfloor+ 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. 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 (French)

Une {\it orientation} d'un graphe~$G$ est un digraphe~$D$ obtenu á partir de $G$ en remplaçant chaque arête par exactement un des deux arcs possibles avec les mêmes extremités. Pour tout $v\in V(G)$, le {\it dégré entrant} de $v$ dans $D$, noté $d^-_D(v)$, est le nombre d'arcs de $D$ ayant $v$ pour tête. Une orientation~$D$ de $G$ est {\it propre} si~$d^-_D(u)\neq d^-_D(v)$, pour tout~$uv\in E(G)$. L'{\it indice d'orientation propre} d'un graphe $G$, noté~$\po(G)$, est le plus petit dégré maximum d'une orientation propre de $G$. Dans ce papier, nous prouvons que $\po(G) \leq \left\lfloor \left(\Delta(G) + \sqrt{\Delta(G)}\right)/2 \right\rfloor+ 1$ si~$G$ est un graphe biparti, et~$\po(G)\leq 4$ si~$G$ est un arbre. Il est connu que~$\po(G)\leq \Delta(G)$, pour tout graphe~$G$. En revancche, nous prouvons que décider si~$\po(G)\leq \Delta(G)-1$ est déjá un probléme $\NP$-complet. Nous montrons aussi qu'il est $\NP$-complet de décider si~$\po(G)\leq 2$ pour un graphe planaire subcubique~$G$. Enfin nous montrons qu'il est $\NP$-complet de décider si $\po(G)\leq 3$ pour un graphe planaire biparti~$G$ de dégré maximum~5.

Additional details