The Complexity of the Proper Orientation Number

Abstract

Graph orientation is a well-studied area of graph theory. A proper orientation of a graph $G=(V,E)$ is an orientation $D$ of $E(G)$ such that for every two adjacent vertices $v$ and $u$, $d_D^{-}(v)\ne d_D^{-}(u)$ where $d_D^{-}(v)$ is the number of edges with head $v$ in $D$. The proper orientation number of $G$ is defined as $\overrightarrow{\chi }(G)=\underset{D\in \Gamma }{\min }\underset{v\in V(G)}{\max }{d}_D^{-}(v)$ where $\Gamma$ is the set of proper orientations of $G$. We have $\chi (G)-1\le \overrightarrow{\chi }(G)\le \Delta (G)$. We show that, it is $\mathbf{NP}$-complete to decide whether $\overrightarrow{\chi }(G)=2$, for a given planar graph $G$. Also, we prove that there is a polynomial time algorithm for determining the proper orientation number of 3-regular graphs. In sharp contrast, we will prove that this problem is $\mathbf{NP}$-hard for 4-regular graphs.

10 pages, 2 figures. Submitted to Information Processing Letters

References in corpus (1)

• Unifying two Graph Decompositions with Modular Decomposition

Cited by in corpus (5)

• Is there any polynomial upper bound for the universal labeling of graphs?
• Note on semi-proper orientations of outerplanar graphs
• Proper 3-orientations of bipartite planar graphs with minimum degree at least 3
• Proper orientations and proper chromatic number
• Proper Orientation Number of Triangle-free Bridgeless Outerplanar Graphs