Akbari et al.'s conjecture on avoiding forbidden out-degree lists

From papers

Let GG be a graph, and let F:V(G)2NF:V(G)\to 2^N assign a set of forbidden out-degrees to each vertex. An orientation OO of GG is FF-avoiding if dO+(v)F(v)d^+_O(v)\notin F(v) for every vV(G)v\in V(G). Akbari et al.'s conjecture. If

F(v)12(dG(v)1)|F(v)|\leq \frac{1}{2}(d_G(v)-1)

for every vV(G)v\in V(G), then GG is FF-avoiding. The conjecture strengthens the known bound F(v)dG(v)/4|F(v)|\leq d_G(v)/4 for which an FF-avoiding orientation is guaranteed; its resolution is not established in the supplied source.

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

Xinxin Ma and Hongliang Lu, “A characterization on orientations of graphs avoiding given lists on out-degrees”, arXiv:2310.15650 (2023).

Solutions 0

No solutions have been posted yet.