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

From papers

Let k3k\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.

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

No solutions have been posted yet.