Bang-Jensen–Bessy–Thomassé conjecture on cycles and girth

Let kk and gg be positive integers, and let f(k,g)f(k,g) be the minimum integer such that every finite simple digraph of girth gg and minimum outdegree at least f(k,g)f(k,g) contains kk vertex-disjoint directed cycles. The circular digraph construction described in the source gives f(k,g)gg1kf(k,g)\geq \left\lceil\frac{g}{g-1}k\right\rceil. Bang-Jensen–Bessy–Thomassé conjecture.

f(k,g)=gg1k.f(k,g)=\left\lceil\frac{g}{g-1}k\right\rceil.

The conjecture is presented as a proposed strengthening in terms of girth, but this paper disproves it, so the conjecture is refuted.

Sources & referencesView supporting material

Primary source

Yandong Bai and Yannis Manoussakis, “On the number of vertex-disjoint cycles in digraphs”, arXiv:1805.02999 (2018).

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.