The asymptotic conjecture for directed cycle packing and covering
The asymptotic conjecture for directed cycle packing and covering
Let be fixed. For a directed graph , let be the maximum number of pairwise arc-disjoint directed -cycles, and let be the minimum number of arcs whose removal makes free of directed -cycles.
Asymptotic directed-cycle packing and covering conjecture. For all sufficiently large , every -vertex directed graph satisfies
The conjecture proposes improving the paper's dense-case bound with constant (and for ) to . It is stated only asymptotically in the number of vertices.
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
Raphael Yuster, “Packing and covering a given directed graph in a directed graph”, arXiv:2312.01901 (2023).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.