A necessary and sufficient condition for the existence of $\{p,p+1,q-1,q\}$-orientations in simple graphs

Abstract

Let $G$ be a simple graph and let $p$ and $q$ be two integer-valued functions on $V(G)$ with $p<q$ in which for each $v\in V(G)$, $q(v)\ge \frac{1}{2}{d}_G(v)$ and $p(v)\ge \frac{1}{2}q(v)-2$. In this note, we show that $G$ has an orientation such that for each vertex $v$, $d_G^{+}(v)\in \{p(v),p(v)+1,q(v)-1,q(v)\}$ if and only if it has an orientation such that for each vertex $v$, $p(v)\le d_G^{+}(v)\le q(v)$ where $d_G^{+}(v)$ denotes the out-degree of $v$ in $G$. From this result, we refine a result due to Addario-Berry, Dalal, and Reed (2008) in bipartite simple graphs on the existence of degree constrained factors.