Institute of Mathematics

of the Czech Academy of Sciences
 
 
 
 

Czechoslovak Mathematical Journal, Vol. 72, No. 1, pp. 39-57, 2022

Packing four copies of a tree into a complete bipartite graph

Liqun Pu, Yuan Tang, Xiaoli Gao

Received June 18, 2020.   Published online December 13, 2021.
Abstract:  In considering packing three copies of a tree into a complete bipartite graph, H. Wang (2009) gives a conjecture: For each tree $T$ of order $n$ and each integer $k\geq2$, there is a $k$-packing of $T$ in a complete bipartite graph $B_{n+k-1}$ whose order is $n+k-1$. We prove the conjecture is true for $k=4$.
Keywords:  packing; bipartite packing; embedding
Classification MSC:  05C05, 05C70
DOI:  10.21136/CMJ.2021.0249-20
PDF available at:  Springer   Institute of Mathematics CAS   Digital Mathematics Library
References:
[1] J.-L. Fouquet, A. P. Wojda: Mutual placement of bipartite graphs. Discrete Math. 121 (1993), 85-92. DOI 10.1016/0012-365X(93)90540-A | MR 1246160 | Zbl 0791.05080
[2] A. M. Hobbs, B. A. Bourgeois, J. Kasiraj: Packing trees in complete graphs. Discrete Math. 67 (1987), 27-42. DOI 10.1016/0012-365X(87)90164-6 | MR 0908184 | Zbl 0642.05043
[3] H. Wang: Packing two forests into a bipartite graph. J. Graph Theory 23 (1996), 209-213. DOI 10.1002/(SICI)1097-0118(199610)23:2<209::AID-JGT12>3.0.CO;2-B | MR 1408349 | Zbl 0858.05089
[4] H. Wang: Packing three copies of a tree into a complete bipartite graph. Ann. Comb. 13 (2009), 261-269. DOI 10.1007/s00026-009-0022-0 | MR 2529729 | Zbl 1229.05233
[5] H. Wang, N. Sauer: The chromatic number of the two-packings of a forest. The Mathematics of Paul Erdős. Vol. II. Algorithms and Combinatorics 14. Springer, Berlin (1997), 99-120. DOI 10.1007/978-3-642-60406-5_11 | MR 1425209 | Zbl 0876.05029
[6] D. B. West: Introduction to Graph Theory. Prentice-Hall, Upper Saddle River (1996). MR 1367739 | Zbl 0845.05001
[7] M. Woźniak: Packing of graphs and permutations - a survey. Discrete Math. 276 (2004), 379-391. DOI 10.1016/S0012-365X(03)00296-6 | MR 2046650 | Zbl 1031.05041
[8] H. P. Yap: Packing of graphs - a survey. Discrete Math. 72 (1988), 395-404. DOI 10.1016/0012-365X(88)90232-4 | MR 0975562 | Zbl 0685.05036
Affiliations:   Liqun Pu (corresponding author), Yuan Tang, Xiaoli Gao, School of Mathematics and Statistics of Zhengzhou University, 100 Science Avenue, Zhengzhou 450001, P. R. China, e-mail: liqunpu@sina.com, yuantang009@163.com, xiaoligao68@163.com
Springer subscribers can access the papers on Springer website.
[List of online first articles] [Contents of Czechoslovak Mathematical Journal] [Full text of the older issues of Czechoslovak Mathematical Journal at DML-CZ]
© Institute of Mathematics CAS, 2026



 
PDF available at:


Springer
for subscribers
···

Institute of Mathematics CAS
free access
···

Digital Mathematics Library
free access