Akbari–Dalirrooyfard–Ehsani–Ozeki–Sherkati conjecture on forbidden out-degrees
Akbari–Dalirrooyfard–Ehsani–Ozeki–Sherkati conjecture on forbidden out-degrees
Let be a loopless -regular graph, with parallel edges permitted, and let be a list of forbidden out-degrees. An orientation is -avoiding if no vertex has out-degree in . Akbari–Dalirrooyfard–Ehsani–Ozeki–Sherkati conjecture. If , then admits an -avoiding orientation. The bound is tight if true: has no -avoiding orientation for . The conjecture is known for bipartite graphs, cliques, and regular graphs of degree at most , while the general case remains open; the source proves it for .
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
Sign in to submit a solution.
No solutions have been posted yet.