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

About 2 years old · traced to

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,…,2k−1}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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.