Mathematics

CLC number: O157.5

Packing 4-Partite Tree into Complete 4-Partite Graph

Department of Mathematics, Suzhou University of Science and Technology, Suzhou 215009, Jiangsu, China

Received: 20 June 2023

Abstract

For graphs G and H, an embedding of G into H is an injection $\varphi :V(G)\to V(H)$ such that $\varphi (a)\varphi (b)\in E(H)$ whenever $ab\in E(G)$. A packing of p graphs $G_{\mathrm{1}},G_{\mathrm{2}},\cdots ,G_p$ into $H$is a p-tuple $\Phi =({\varphi }_{\mathrm{1}},{\varphi }_{\mathrm{2}},\cdots ,{\varphi }_p)$ such that, for $i=\mathrm{1,2},\cdots ,p$, ${\varphi }_i$ is an embedding of $G_i$ into H and the p sets ${\varphi }_i(E(G_i))$ are mutually disjoint. Motivated by the "Tree Packing Conjecture" made by Gy$\dot{\mathrm{a}}$rf$\dot{\mathrm{a}}$s and Lehel, Wang Hong conjectured that for each k-partite tree, there is a packing of two copies of $T({X})$ into a complete k-partite graph $B_{n+m}({Y})$, where $m=\lfloor k/\mathrm{2}\rfloor$. In this paper, we confirm this conjecture for $k=\mathrm{4}$.