Proper Orientation Number of Triangle-free Bridgeless Outerplanar Graphs

Abstract

An orientation of $G$ is a digraph obtained from $G$ by replacing each edge by exactly one of two possible arcs with the same endpoints. We call an orientation \emph{proper} if neighbouring vertices have different in-degrees. The proper orientation number of a graph $G$, denoted by $\vec{\chi }(G)$, is the minimum maximum in-degree of a proper orientation of G. Araujo et al. (Theor. Comput. Sci. 639 (2016) 14--25) asked whether there is a constant $c$ such that $\vec{\chi }(G)\le c$ for every outerplanar graph $G$ and showed that $\vec{\chi }(G)\le 7$ for every cactus $G.$ We prove that $\vec{\chi }(G)\le 3$ if $G$ is a triangle-free $2$-connected outerplanar graph and $\vec{\chi }(G)\le 4$ if $G$ is a triangle-free bridgeless outerplanar graph.