Geodesic
Packing four copies of a tree into a complete bipartite graph
Czechoslovak Mathematical Journal, Tome 72 (2022) no. 1, pp. 39-57
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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$.
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$.
DOI : 10.21136/CMJ.2021.0249-20
Classification : 05C05, 05C70
Keywords: packing; bipartite packing; embedding 
@article{10_21136_CMJ_2021_0249_20,
     author = {Pu, Liqun and Tang, Yuan and Gao, Xiaoli},
     title = {Packing four copies of a tree into a complete bipartite graph},
     journal = {Czechoslovak Mathematical Journal},
     pages = {39--57},
     year = {2022},
     volume = {72},
     number = {1},
     doi = {10.21136/CMJ.2021.0249-20},
     mrnumber = {4389105},
     zbl = {07511552},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2021.0249-20/}
}
TY  - JOUR
AU  - Pu, Liqun
AU  - Tang, Yuan
AU  - Gao, Xiaoli
TI  - Packing four copies of a tree into a complete bipartite graph
JO  - Czechoslovak Mathematical Journal
PY  - 2022
SP  - 39
EP  - 57
VL  - 72
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2021.0249-20/
DO  - 10.21136/CMJ.2021.0249-20
LA  - en
ID  - 10_21136_CMJ_2021_0249_20
ER  - 
%0 Journal Article
%A Pu, Liqun
%A Tang, Yuan
%A Gao, Xiaoli
%T Packing four copies of a tree into a complete bipartite graph
%J Czechoslovak Mathematical Journal
%D 2022
%P 39-57
%V 72
%N 1
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2021.0249-20/
%R 10.21136/CMJ.2021.0249-20
%G en
%F 10_21136_CMJ_2021_0249_20
Pu, Liqun; Tang, Yuan; Gao, Xiaoli. Packing four copies of a tree into a complete bipartite graph. Czechoslovak Mathematical Journal, Tome 72 (2022) no. 1, pp. 39-57. doi: 10.21136/CMJ.2021.0249-20

[1] Fouquet, J.-L., Wojda, A. P.: Mutual placement of bipartite graphs. Discrete Math. 121 (1993), 85-92. | DOI | MR | JFM

[2] Hobbs, A. M., Bourgeois, B. A., Kasiraj, J.: Packing trees in complete graphs. Discrete Math. 67 (1987), 27-42. | DOI | MR | JFM

[3] Wang, H.: Packing two forests into a bipartite graph. J. Graph Theory 23 (1996), 209-213. | DOI | MR | JFM

[4] Wang, H.: Packing three copies of a tree into a complete bipartite graph. Ann. Comb. 13 (2009), 261-269. | DOI | MR | JFM

[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 | MR | JFM

[6] West, D. B.: Introduction to Graph Theory. Prentice-Hall, Upper Saddle River (1996). | MR | JFM

[7] Woźniak, M.: Packing of graphs and permutations - a survey. Discrete Math. 276 (2004), 379-391. | DOI | MR | JFM

[8] Yap, H. P.: Packing of graphs - a survey. Discrete Math. 72 (1988), 395-404. | DOI | MR | JFM

Cité par Sources :