Opuscula Math. 44, no. 5 (2024), 673-688
https://doi.org/10.7494/OpMath.2024.44.5.673
Opuscula Mathematica
Seven largest trees pack
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.
- 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
- 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
- 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
- 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
- R.L. Graham, M. Grötschel, L. Lovász (eds), Handbook of Combinatorics, vol. 1, Elsevier Science B.V., Amsterdam, 1995.
- R.L. Graham, M. Grötschel, L. Lovász (eds), Handbook of Combinatorics, vol. 2, Elsevier Science B.V., Amsterdam, 1995.
- 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.
- B. Janzer, R. Montgomery, Packing the largest trees in the tree packing conjecture, arXiv:2403.10515, (2024).
- 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
- 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
- A. Żak, Packing large trees of consecutive orders, 340 (2017), no. 2, 252-263. https://doi.org/10.1016/j.disc.2016.07.022
- 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
- Communicated by Mirko Horňák.
- Received: 2023-05-20.
- Revised: 2024-05-17.
- Accepted: 2024-05-21.
- Published online: 2024-07-01.
