The asymptotic k/2k/2 conjecture for directed cycle packing and covering

About 3 years old · traced to

Let k≥3k\ge 3 be fixed. For a directed graph DD, let νk(D)\nu_k(D) be the maximum number of pairwise arc-disjoint directed kk-cycles, and let τk(D)\tau_k(D) be the minimum number of arcs whose removal makes DD free of directed kk-cycles.

Asymptotic directed-cycle packing and covering conjecture. For all sufficiently large nn, every nn-vertex directed graph DD satisfies

τk(D)≤(k/2)νk(D).\tau_k(D)\le (k/2)\nu_k(D).

The conjecture proposes improving the paper's dense-case bound with constant 2k/32k/3 (and 25/825/8 for k=5k=5) to k/2k/2. It is stated only asymptotically in the number of vertices.

References

Primary source

Raphael Yuster, “Packing and covering a given directed graph in a directed graph”, arXiv:2312.01901 (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.