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

At least 2 years old · documented by

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 v∈V(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 v∈V(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.

References

Primary source

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

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.