Proper Orientations of Planar Bipartite Graphs

Abstract

An orientation of a graph $G$ is proper if any two adjacent vertices have different indegrees. The proper orientation number $\overrightarrow{\chi }(G)$ of a graph $G$ is the minimum of the maximum indegree, taken over all proper orientations of $G$. In this paper, we show that a connected bipartite graph may be properly oriented even if we are only allowed to control the orientation of a specific set of edges, namely, the edges of a spanning tree and all the edges incident to one of its leaves. As a consequence of this result, we prove that 3-connected planar bipartite graphs have proper orientation number at most 6. Additionally, we give a short proof that $\overrightarrow{\chi }(G)\le 4$, when $G$ is a tree and this proof leads to a polynomial-time algorithm to proper orient trees within this bound.

5 pages