Generalized forbidden out-degree conjecture

Let GG be a loopless graph, and let d(v)d(v) denote the degree of each vertex vV(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 vV(G)v\in V(G). Generalized forbidden out-degree conjecture. If F(v)<12d(v)|F(v)|<\tfrac{1}{2}d(v) for all vV(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.

Sources & referencesView supporting material

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.