Generalized forbidden out-degree conjecture

About 2 years old · traced to

Let GG be a loopless graph, and let d(v)d(v) denote the degree of each vertex v∈V(G)v\in V(G). Given a function F:V(G)→2NF:V(G)\to 2^{\mathbb N}, an orientation is FF-avoiding if its out-degree dD+(v)d_D^+(v) satisfies dD+(v)∉F(v)d_D^+(v)\notin F(v) for every v∈V(G)v\in V(G). Generalized forbidden out-degree conjecture. If ∣F(v)∣<12d(v)|F(v)|<\tfrac{1}{2}d(v) for all v∈V(G)v\in V(G), then GG admits an FF-avoiding orientation. This generalization is motivated by allowing the degree and forbidden list to vary from vertex to vertex. The source verifies it for some new cases, including 2-degenerate graphs and forbidden sets with specific structure, but the full statement remains open.

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.