The existence of $\{p,q\}$-orientations in edge-connected graphs

Abstract

In 1976 Frank and Gy{á}rf{á}s gave a necessary and sufficient condition for the existence of an orientation in an arbitrary graph $G$ such that for each vertex $v$, the out-degree $d_G^{+}(v)$ of it satisfies $p(v)\le d_G^{+}(v)\le q(v)$, where $p$ and $q$ are two integer-valued functions on $V(G)$ with $p\le q$. In this paper, we give a sufficient edge-connectivity condition for the existence of an orientation in $G$ such that for each vertex $v$, $d_G^{+}(v)\in \{p(v),q(v)\}$, provided that for each vertex $v$, $p(v)\le \frac{1}{2}{d}_G(v)\le q(v)$, $|q(v)-p(v)|\le k$, and there is $t(v)\in \{p(v),q(v)\}$ in which $|E(G)|={\sum }_{v\in V(G)}t(v)$. This result is a generalization of a theorem due to Thomassen (2012) on the existence of modulo orientations in highly edge-connected graphs.

arXiv admin note: text overlap with arXiv:1702.07039