On orientations with forbidden out-degrees

Abstract

Let $G$ be a $d$-regular graph and let $F\subseteq \{0,1,2,\dots ,d\}$ be a list of forbidden out-degrees. Akbari, Dalirrooyfard, Ehsani, Ozeki, and Sherkati conjectured that if $|F|<\frac{1}{2}d$, then $G$ should admit an $F$-avoiding orientation, i.e., an orientation where no out-degrees are in the forbidden list $F$. The conjecture is known for $d\le 4$ due to work of Ma and Lu, and here we extend this to $d\le 6$. The conjecture has also been studied in a generalized version, where $d,F$ are changed from constant values to functions $d(v),F(v)$ that vary over all $v\in V(G)$. We provide support for this generalized version by verifying it for some new cases, including when $G$ is 2-degenerate and when every $F(v)$ has some specific structure.

10 pages, 2 figures