The Complexity of the Proper Orientation Number

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) \neq 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χ (G) =\displaystyle \min_{D\in Γ} \displaystyle\max_{v\in V(G)} d^{-}_{D}(v)$ where $Γ$ is the set of proper orientations of $G$. We have $χ(G)-1 \leq \overrightarrowχ (G)\leq Δ(G)$. We show that, it is $\mathbf{NP}$-complete to decide whether $\overrightarrowχ(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.

No reviews yet.

No comments yet.