Degree condition for maximum-length cycles in bipartite digraphs

About 15 years old · traced to

Let DD be a bipartite digraph with colour classes XX and YY such that ∣X∣=a≤b=∣Y∣|X|=a\leq b=|Y|. For vertices uu and vv in opposite colour classes with uv∉A(D)uv\notin A(D), consider the degree condition

d+(u)+d−(v)>a+b+22.d^+(u)+d^-(v)>\frac{a+b+2}{2}.

Maximum-cycle degree conjecture. If this inequality holds whenever uu and vv lie in opposite colour classes and uv∉A(D)uv\notin A(D), then DD contains an oriented cycle of length 2a2a.

This is an Ore-type sufficient condition for a bipartite digraph to contain a cycle meeting every vertex of its smaller colour class. The source states that the conjecture is proved in the balanced case a=ba=b, while the general case remains open.

References

Primary source

Janusz Adamus and Lech Adamus, “A degree condition for cycles of maximum length in bipartite digraphs”, arXiv:1101.4973 (2012).

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.