New interface

On the proper orientation number of bipartite graphs

4 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
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.
Keywords :
Document type :
Reports (Research report)
Domain :

Cited literature [6 references]

https://hal.inria.fr/hal-00957453
Contributor : Julio Araujo Connect in order to contact the contributor
Submitted on : Monday, March 10, 2014 - 7:56:42 PM
Last modification on : Friday, November 4, 2022 - 6:52:06 PM
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⟩

Record views