Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2601.13085 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908774488342528 |
|---|---|
| author | Cisiński, Maciej Żak, Andrzej |
| author_facet | Cisiński, Maciej Żak, Andrzej |
| contents | Two digraphs of order $n$ are said to pack if they can be found as edge-disjoint subgraphs of the complete digraph of order $n$. It is well established that if the sum of the sizes of the two digraphs is at most $2n-2$, then they pack, with this bound being sharp. However, it is sufficient for the size of the smaller digraph to be only slightly below $n$ for the sum of their sizes to significantly exceed this threshold while still guaranteeing the existence of a packing.
In 1985, Wojda conjectured that for any $2 \leq m \leq n/2$, if one digraph has size at most $n - m$ and the other has size less than $2n - \lfloor n/m \rfloor$, then the two digraphs pack. It was previously known that this conjecture holds for $m = Ω(\sqrt{n})$. In this paper, we confirm it for $m \geq 93$ and $n \geq 31m$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_13085 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Further progress on Wojda's conjecture Cisiński, Maciej Żak, Andrzej Combinatorics Two digraphs of order $n$ are said to pack if they can be found as edge-disjoint subgraphs of the complete digraph of order $n$. It is well established that if the sum of the sizes of the two digraphs is at most $2n-2$, then they pack, with this bound being sharp. However, it is sufficient for the size of the smaller digraph to be only slightly below $n$ for the sum of their sizes to significantly exceed this threshold while still guaranteeing the existence of a packing. In 1985, Wojda conjectured that for any $2 \leq m \leq n/2$, if one digraph has size at most $n - m$ and the other has size less than $2n - \lfloor n/m \rfloor$, then the two digraphs pack. It was previously known that this conjecture holds for $m = Ω(\sqrt{n})$. In this paper, we confirm it for $m \geq 93$ and $n \geq 31m$. |
| title | Further progress on Wojda's conjecture |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2601.13085 |