Speaker: Peter Bradshaw (UIUC)
Title: List-avoiding orientations
Given a graph G with a set F(v) of forbidden values at each vertex v, an F-avoiding orientation of G is an orientation in which the out-degree at v is not in F(v) for each vertex v. Akbari, Dalirrooyfard, Ehsani, Ozeki, and Sherkati conjectured that if |F(v)| < deg(v)/2 for each v, then G has an F-avoiding orientation, and they showed that this statement is true when the upper bound is replaced by deg(v)/4. In this paper, we take a step toward this conjecture by proving that if |F(v)| < deg(v)/3 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 1/3 can be increased to 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.
