Wojda's conjecture on packing digraphs

Let DD and DD' be digraphs, and let A(D)|A(D)| denote the size of DD, meaning its number of arcs. For every integer nn and every mm satisfying

2mn2,2\leq m\leq \frac{n}{2},

write μ(n,k)\mu(n,k) for the smallest number such that there exist digraphs DD and DD' of order nn, with A(D)=k|A(D)|=k and A(D)=μ(n,k)|A(D')|=\mu(n,k), that do not pack. Wojda's conjecture. For every mm satisfying 2mn22\leq m\leq \frac{n}{2},

μ(n,nm)=2nnm.\mu(n,n-m)=2n-\left\lfloor\frac{n}{m}\right\rfloor.

Equivalently, the condition that one digraph has size at most nmn-m and the other has size less than 2nn/m2n-\lfloor n/m\rfloor guarantees that the two digraphs pack. The paper confirms the conjecture for m93m\geq 93 and n31mn\geq 31m; the general statement remains open.

Sources & referencesView supporting material

Primary source

Maciej Cisiński and Andrzej Żak, “Further progress on Wojda's conjecture”, arXiv:2601.13085 (2026).

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.