Orientations of graphs avoiding non-consecutive integers on out-degrees
Let $G$ be a graph and $F: V(G) \to 2^N$ be a set function. The graph $G$ is said to be \emph{F-avoiding} if there exists an orientation $O$ of $G$ such that $d^+_O(v)\not \in F(v)$ for every $v\in V(G),$ where $d^+_O(v)$ denotes the out-degree of $v$ in the directed graph $G$ with respect to $O$. In this paper, we obtain the following result: if the set $F(v)$ satisfies $|F(v)|\leq \frac{1}{2}(d_G(v)-1)$ and $F(v)$ contains no two consecutive integers, then $G$ is \emph{F-avoiding}. In fact, we give a Gallai-Edmonds type characterization if the set $F(v)$ satisfies $|F(v)|\leq \lceil\frac{1}{2}d_G(v)\rceil$ and $F(v)$ contains no two consecutive integers.