List-avoiding orientations

Abstract

Given a graph $G$ with a set $F(v)$ of forbidden values at each $v\in V(G)$, an $F$-avoiding orientation of $G$ is an orientation in which $de{g}^{+}(v)\notin F(v)$ for each vertex $v$. Akbari, Dalirrooyfard, Ehsani, Ozeki, and Sherkati conjectured that if $|F(v)|<\frac{1}{2}deg(v)$ for each $v\in V(G)$, then $G$ has an $F$-avoiding orientation, and they showed that this statement is true when $\frac{1}{2}$ is replaced by $\frac{1}{4}$. In this paper, we take a step toward this conjecture by proving that if $|F(v)|<\lfloor \frac{1}{3}deg(v)\rfloor$ for each vertex $v$, then $G$ has an $F$-avoiding orientation. Furthermore, we show that if the maximum degree of $G$ is subexponential in terms of the minimum degree, then this coefficient of $\frac{1}{3}$ can be increased to $\sqrt{2}-1-o(1)\approx 0.414$. Our main tool is a new sufficient condition for the existence of an $F$-avoiding orientation based on the Combinatorial Nullstellensatz of Alon and Tarsi.