Skip to Main content Skip to Navigation
Reports

On the proper orientation number of bipartite graphs

Abstract : 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.
Complete list of metadatas

Cited literature [6 references]  Display  Hide  Download

https://hal.inria.fr/hal-00957453
Contributor : Julio Araujo <>
Submitted on : Monday, March 10, 2014 - 7:56:42 PM
Last modification on : Thursday, October 22, 2020 - 3:37:15 AM
Long-term archiving on: : Tuesday, June 10, 2014 - 12:10:53 PM

File

RR-8492.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00957453, version 1

Citation

Julio Araujo, Nathann Cohen, Susanna F. de Rezende, Frédéric Havet, Phablo Moura. On the proper orientation number of bipartite graphs. [Research Report] RR-8492, INRIA. 2014, pp.23. ⟨hal-00957453⟩

Share

Metrics

Record views

550

Files downloads

465