Bulletin of the
Korean Mathematical Society

ISSN(Print) 1015-8634 ISSN(Online) 2234-3016



Bull. Korean Math. Soc. 2022; 59(2): 345-350

Published online March 31, 2022 https://doi.org/10.4134/BKMS.b210147

Copyright © The Korean Mathematical Society.

Packing trees into complete k-partite graph

Yanling Peng, Hong Wang

Suzhou University of Science and Technology; University of Idaho


In this work, we confirm a weak version of a conjecture proposed by Hong Wang. The ideal of the work comes from the tree packing conjecture made by Gy\'arf\'as and Lehel. Bollob\'as confirms the tree packing conjecture for many small tree, who showed that one can pack $T_1,T_2,\ldots,T_{n/\sqrt{2}}$ into $K_n$ and that a better bound would follow from a famous conjecture of Erd\H{o}s. In a similar direction, Hobbs, Bourgeois and Kasiraj made the following conjecture: Any sequence of trees $T_1,T_2,\ldots,T_n$, with $T_i$ having order $i$, can be packed into $K_{n-1,\lceil n/2\rceil}$. Further Hobbs, Bourgeois and Kasiraj \cite{3} proved that any two trees can be packed into a complete bipartite graph $K_{n-1,\lceil n/2\rceil}$. Motivated by the result, Hong Wang propose the conjecture: For each $k$-partite tree $T(\mathbb{X})$ of order $n$, there is a restrained packing of two copies of $T(\mathbb{X})$ into a complete $k$-partite graph $B_{n+m}(\mathbb{Y})$, where $m=\lfloor\frac{k}{2}\rfloor$. Hong Wong \cite{4} confirmed this conjecture for $k=2$. In this paper, we prove a weak version of this conjecture.

Keywords: Packing of graphs, tree packing conjecture, $k$-partite tree

MSC numbers: 05C70

Supported by: This work was supported by the National NSF of China (no. 12071334, 11871270).

Stats or Metrics

Share this article on :

Related articles in BKMS