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