Opuscula Mathematica
Opuscula Math. 44, no. 5 (2024), 673-688

Seven largest trees pack

Maciej Cisiński
Andrzej Żak
Abstract. The Tree Packing Conjecture (TPC) by Gyárfás states that any set of trees \(T_2,\dots,T_{n-1}, T_n\) such that \(T_i\) has \(i\) vertices pack into \(K_n\). The conjecture is true for bounded degree trees, but in general, it is widely open. Bollobás proposed a weakening of TPC which states that \(k\) largest trees pack. The latter is true if none tree is a star, but in general, it is known only for \(k=5\). In this paper we prove, among other results, that seven largest trees pack.
Keywords: tree, packing, tree packing conjecture.
Mathematics Subject Classification: 05C35, 05C05, 05C70.
Full text (pdf)
References ▼
  1. [1] N. Alon, R. Yuster, The Turán number of sparse spanning graphs, J. Comb. Theory Ser. B 103 (2013), no. 3, 337-343. https://doi.org/10.1016/j.jctb.2013.02.002
  2. [2] J. Balogh, C. Palmer, On the tree packing conjecture, SIAM J. Discrete Math. 27 (2013) no. 4, 1995-2006. https://doi.org/10.1137/120902719
  3. [3] B.A. Bourgeois, A.M. Hobbs, J. Kasiraj, Packing trees in complete graphs, Discrete Math. 67 (1987), 27-42. https://doi.org/10.1016/0012-365X(87)90164-6
  4. [4] J. Böttcher, J. Hladký, D. Piguet, A. Taraz, An approximate version of the tree packing conjecture, Israel J. Math. 211 (2016), 391-446. https://doi.org/10.1007/s11856-015-1277-2
  5. [5] R.L. Graham, M. Grötschel, L. Lovász (eds), Handbook of Combinatorics, vol. 1, Elsevier Science B.V., Amsterdam, 1995.
  6. [6] R.L. Graham, M. Grötschel, L. Lovász (eds), Handbook of Combinatorics, vol. 2, Elsevier Science B.V., Amsterdam, 1995.
  7. [7] A. Gyárfás, J. Lehel, Packing trees of different order into \(K_n\), Combinatorics, Proc. Fifth Hungarian Colloq., Keszthely, (1976), Colloq. Math. Soc. János Bolyai, vol. 18, North-Holland, Amsterdam, 1978, 463-469.
  8. [8] B. Janzer, R. Montgomery, Packing the largest trees in the tree packing conjecture, arXiv:2403.10515, (2024).
  9. [9] F. Joos, J. Kim, D. Kühn, D. Osthus, Optimal packings of bounded degree trees, J. Eur. Math. Soc. (JEMS) 21 (2019), no. 12, 3573-3647. https://doi.org/10.4171/JEMS/909
  10. [10] S. Messuti, V. Rödl, M. Schacht, Packing minor-closed families of graphs into complete graphs, J. Comb. Theory Ser. B 119 (2016), 245-265. https://doi.org/10.1016/j.jctb.2016.03.003
  11. [11] A. Żak, Packing large trees of consecutive orders, 340 (2017), no. 2, 252-263. https://doi.org/10.1016/j.disc.2016.07.022
About the authors ▼
Maciej Cisiński (corresponding author)
https://orcid.org/0009-0001-5106-8764
AGH University of Krakow, Faculty of Applied Mathematics, al. Mickiewicza 30, 30-059 Kraków, Poland
Andrzej Żak
https://orcid.org/0000-0002-3657-1417
AGH University of Krakow, Faculty of Applied Mathematics, al. Mickiewicza 30, 30-059 Kraków, Poland
About the article ▼
Communicated by Mirko Horňák.
Received: 2023-05-20.
Revised: 2024-05-17.
Accepted: 2024-05-21.
Published online: 2024-07-01.
Cite this article as ▼
Maciej Cisiński, Andrzej Żak, Seven largest trees pack, Opuscula Math. 44, no. 5 (2024), 673-688, https://doi.org/10.7494/OpMath.2024.44.5.673.
Download this article's citation as: