| Title:
|
Packing four copies of a tree into a complete bipartite graph (English) |
| Author:
|
Pu, Liqun |
| Author:
|
Tang, Yuan |
| Author:
|
Gao, Xiaoli |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
72 |
| Issue:
|
1 |
| Year:
|
2022 |
| Pages:
|
39-57 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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$. (English) |
| Keyword:
|
packing |
| Keyword:
|
bipartite packing |
| Keyword:
|
embedding |
| MSC:
|
05C05 |
| MSC:
|
05C70 |
| idZBL:
|
Zbl 07511552 |
| idMR:
|
MR4389105 |
| DOI:
|
10.21136/CMJ.2021.0249-20 |
| . |
| Date available:
|
2022-03-25T08:25:25Z |
| Last updated:
|
2024-04-01 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/149572 |
| . |
| Reference:
|
[1] Fouquet, J.-L., Wojda, A. P.: Mutual placement of bipartite graphs.Discrete Math. 121 (1993), 85-92. Zbl 0791.05080, MR 1246160, 10.1016/0012-365X(93)90540-A |
| Reference:
|
[2] Hobbs, A. M., Bourgeois, B. A., Kasiraj, J.: Packing trees in complete graphs.Discrete Math. 67 (1987), 27-42. Zbl 0642.05043, MR 0908184, 10.1016/0012-365X(87)90164-6 |
| Reference:
|
[3] Wang, H.: Packing two forests into a bipartite graph.J. Graph Theory 23 (1996), 209-213. Zbl 0858.05089, MR 1408349, 10.1002/(SICI)1097-0118(199610)23:2<209::AID-JGT12>3.0.CO;2-B |
| Reference:
|
[4] Wang, H.: Packing three copies of a tree into a complete bipartite graph.Ann. Comb. 13 (2009), 261-269. Zbl 1229.05233, MR 2529729, 10.1007/s00026-009-0022-0 |
| Reference:
|
[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. Zbl 0876.05029, MR 1425209, 10.1007/978-3-642-60406-5_11 |
| Reference:
|
[6] West, D. B.: Introduction to Graph Theory.Prentice-Hall, Upper Saddle River (1996). Zbl 0845.05001, MR 1367739 |
| Reference:
|
[7] Woźniak, M.: Packing of graphs and permutations - a survey.Discrete Math. 276 (2004), 379-391. Zbl 1031.05041, MR 2046650, 10.1016/S0012-365X(03)00296-6 |
| Reference:
|
[8] Yap, H. P.: Packing of graphs - a survey.Discrete Math. 72 (1988), 395-404. Zbl 0685.05036, MR 0975562, 10.1016/0012-365X(88)90232-4 |
| . |
