Akbari–Dalirrooyfard–Ehsani–Ozeki–Sherkati conjecture on forbidden out-degrees

From papers

Let GG be a loopless dd-regular graph, with parallel edges permitted, and let F{0,1,,d}F\subseteq\{0,1,\ldots,d\} be a list of forbidden out-degrees. An orientation is FF-avoiding if no vertex has out-degree in FF. Akbari–Dalirrooyfard–Ehsani–Ozeki–Sherkati conjecture. If F<12d|F|<\tfrac{1}{2}d, then GG admits an FF-avoiding orientation. The bound is tight if true: K2k+1K_{2k+1} has no FF-avoiding orientation for F={k,,2k1}F=\{k,\ldots,2k-1\}. The conjecture is known for bipartite graphs, cliques, and regular graphs of degree at most 44, while the general case remains open; the source proves it for d=5,6d=5,6.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Owen Henderschedt and Jessica McDonald, “On orientations with forbidden out-degrees”, arXiv:2406.05095 (2024).

Solutions 0

No solutions have been posted yet.