Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
packing; bipartite packing; embedding
packing; bipartite packing; embedding
Summary:
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\geq 2$, 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$.
References:
[1] Fouquet, J.-L., Wojda, A. P.: 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] Hobbs, A. M., Bourgeois, B. A., Kasiraj, J.: 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] Wang, H.: 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] Wang, H.: 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] Wang, H., Sauer, N.: 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] West, D. B.: Introduction to Graph Theory. Prentice-Hall, Upper Saddle River (1996). MR 1367739 | Zbl 0845.05001
[7] Woźniak, M.: 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] Yap, H. P.: Packing of graphs - a survey. Discrete Math. 72 (1988), 395-404. DOI 10.1016/0012-365X(88)90232-4 | MR 0975562 | Zbl 0685.05036
Search
Partner of
