Seven largest trees pack

• Autorzy: Cisiński Maciej , Żak Andrzej

Identyfikatory

DOI

10.7494/OpMath.2024.44.5.673

• Języki publikacji: EN

Abstrakty

EN

The Tree Packing Conjecture (TPC) by Gyárfás states that any set of trees T2, . . . , Tn−1, Tn such that Ti has i vertices pack into Kn. 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.

Słowa kluczowe

EN

tree; packing; tree packing conjecture

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2024
• Tom: Vol. 44, no. 5
• Strony: 673--688
• Opis fizyczny: Bibliogr. 11 poz., rys.

Twórcy

autor

Cisiński Maciej

• AGH University of Krakow, Faculty of Applied Mathematics, al. Mickiewicza 30, 30–059 Kraków, Poland

• https://orcid.org/0009-0001-5106-8764

autor

Żak Andrzej

• AGH University of Krakow, Faculty of Applied Mathematics, al. Mickiewicza 30, 30–059 Kraków, Poland

• https://orcid.org/0000-0002-3657-1417

Bibliografia

• [1] N. Alon, R. Yuster, The Turán number of sparse spanning graphs, J. Comb. Theory Ser. B 103 (2013), no. 3, 337–343.
• [2] J. Balogh, C. Palmer, On the tree packing conjecture, SIAM J. Discrete Math. 27 (2013), no. 4, 1995–2006.
• [3] B.A. Bourgeois, A.M. Hobbs, J. Kasiraj, Packing trees in complete graphs, Discrete Math. 67 (1987), 27–42.
• [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.
• [5] R.L. Graham, M. Grötschel, L. Lovász (eds), Handbook of Combinatorics, vol. 1, Elsevier Science B.V., Amsterdam, 1995.
• [6] R.L. Graham, M. Grötschel, L. Lovász (eds), Handbook of Combinatorics, vol. 2, Elsevier Science B.V., Amsterdam, 1995.
• [7] A. Gyárfás, J. Lehel, Packing trees of different order into Kn, Combinatorics, Proc. Fifth Hungarian Colloq., Keszthely, (1976), Colloq. Math. Soc. János Bolyai, vol. 18, North-Holland, Amsterdam, 1978, 463–469.
• [8] B. Janzer, R. Montgomery, Packing the largest trees in the tree packing conjecture, arXiv:2403.10515, (2024).
• [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.
• [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.
• [11] A. Żak, Packing large trees of consecutive orders, Discrete Math. 340 (2017), no. 2, 252–263.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023)