## Abstract

The Gyárfás tree packing conjecture states that any set of n-1 trees T_{1}, T_{2}, Tn-1 such that Ti has n-i+1 vertices packs into K_{n} (for n large enough). We show that t = 1 10n1/4 trees T_{1}, T_{2},Tt such that Ti has n-i+1 vertices packs into K_{n+1} (for n large enough). We also prove that any set of t = 1 10n1/4 trees T_{1}, T_{2}, Tt such that no tree is a star and Ti has n-i+1 vertices packs into Kn (for n large enough). Finally, we prove that t = 1 4n1/3 trees T_{1}, T_{2}, Tt such that Ti has n - i + 1 vertices packs into Kn as long as each tree has maximum degree at least 2n^{2/3} (for n large enough). One of the main tools used in the paper is the famous spanning tree embedding theorem of Komlós, Sárközy, and Szemerédi [Combin. Probab. Comput., 10 (2001), pp. 397-416].

Original language | English |
---|---|

Pages (from-to) | 1995-2006 |

Number of pages | 12 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 27 |

Issue number | 4 |

DOIs | |

State | Published - 2013 |

## Keywords

- Packing
- Tree
- Tree packing