论文标题
避免列表的方向
List-avoiding orientations
论文作者
论文摘要
给定一个$ f（v）$ f（v）$ f（g）$中的$ f（v）$的图形$ g $，$ g $ g $的$ f $ - 避免$ f $ g $的方向是$ deg^+（v）\ in f（v）in f（v）$ in f（v）$ in f（v）$ in f（v）$ in f pertertex $ v $ v $。 Akbari，Dalirrooyfard，Ehsani，Ozeki和Sherkati猜想，如果$ | f（v）| <\ frac {1} {2} deg（v）$ in v（g）$中的每个$ v \，然后$ g $具有$ f $ - 避免的方向，他们表明，当$ \ frac {1} {2} $替换为$ \ frac {1} $时，此语句是正确的。在本文中，我们通过证明$ | f（v）|迈出了这一猜想的一步。 <\ lfloor \ frac {1} {3} deg（v）\ rfloor $对于每个顶点$ v $，然后$ g $具有$ f $ - 避免的方向。此外，我们表明，如果$ g $的最大程度是最低度的次指定性，则可以将$ \ frac {1} {3} $的系数增加到$ \ sqrt {2} -1 -o（1 -o（1）-o（1）\ of of 0.414 $。我们的主要工具是基于Alon和Tarsi组合的Nullstellensatz存在$ F $避免$ F $的方向的新的足够条件。
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 $deg^+(v) \not \in 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.
