List-avoiding orientations

DOI10.1007/S00493-024-00109-ZMaRDI QIDQ6411226zbMATH OpenFDO

Authors Yaobin Chen, Hao Ma, Bojan Mohar, Hehui Wu

Publication date 19 September 2022

Full work available at URL https://doi.org/10.1007/S00493-024-00109-Z

Mathematics Subject Classification ID

Graph theory (05Cxx)

Abstract: Given a graph $G$ with a set $F(v)$ of forbidden values at each $vinV(G)$, an $F$-avoiding orientation of $G$ is an orientation in which $de{g}^{+}(v)otinF(v)$ for each vertex $v$. Akbari, Dalirrooyfard, Ehsani, Ozeki, and Sherkati conjectured that if $|F(v)|<frac12deg(v)$ for each $vinV(G)$, then $G$ has an $F$-avoiding orientation, and they showed that this statement is true when $frac12$ is replaced by $frac14$. In this paper, we take a step toward this conjecture by proving that if $|F(v)|<lfloorfrac13deg(v)floor$ 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 $frac13$ can be increased to $sqrt2-1-o(1)approx0.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.

This page was built for publication: List-avoiding orientations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6411226)