Opuscula Math. 37, no. 4 (2017), 589-595
http://dx.doi.org/10.7494/OpMath.2017.37.4.589

Opuscula Mathematica

# Toward Wojda's conjecture on digraph packing

Jerzy Konarski
Andrzej Żak

Abstract. Given a positive integer $$m\leq n/2$$, Wojda conjectured in 1985 that if $$D_1$$ and $$D_2$$ are digraphs of order $$n$$ such that $$|A(D_1)|\leq n-m$$ and $$|A(D_2)|\leq 2n-\lfloor n/m\rfloor-1$$ then $$D_1$$ and $$D_2$$ pack. The cases when $$m=1$$ or $$m = n/2$$ follow from known results. Here we prove the conjecture for $$m\geq\sqrt{8n}+418275$$.

Keywords: packing, digraph, size.

Mathematics Subject Classification: 05C35.

Full text (pdf)

1. A. Benhocine, H.J. Veldman, A.P. Wojda, Packing of digraphs, Ars Combin. 22 (1986), 43-49.
2. E. Györi, A. Kostochka, A. McConvey, D. Yager, Toward Żak's conjecture on graph packing, J. Combin. 7 (2016) 2, 307-340.
3. A.P. Wojda, Research problems (Problem 69), Discrete Math. 57 (1985), 209-210.
4. A.P. Wojda, M. Woźniak, Packing and extremal digraphs, Ars Combin. 20 B (1985), 71-73.
• Jerzy Konarski
• AGH University of Science and Technology, Faculty of Applied Mathematics, al. A. Mickiewicza 30, 30-059 Krakow, Poland
• Andrzej Żak
• AGH University of Science and Technology, Faculty of Applied Mathematics, al. A. Mickiewicza 30, 30-059 Krakow, Poland
• Communicated by Gyula O.H. Katona.
• Revised: 2016-11-14.
• Accepted: 2016-11-15.
• Published online: 2017-04-28.