Geodesic
Generalizations of the tree packing conjecture
Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 3, pp. 569-582.

Voir la notice de l'article provenant de la source Library of Science

The Gyárfás tree packing conjecture asserts that any set of trees with 2,3,...,k vertices has an (edge-disjoint) packing into the complete graph on k vertices. Gyárfás and Lehel proved that the conjecture holds in some special cases. We address the problem of packing trees into k-chromatic graphs. In particular, we prove that if all but three of the trees are stars then they have a packing into any k-chromatic graph. We also consider several other generalizations of the conjecture.
Keywords: packing, tree packing 
@article{DMGT_2012_32_3_a14,
     author = {Gerbner, D\'aniel and Keszegh, Bal\'azs and Palmer, Cory},
     title = {Generalizations of the tree packing conjecture},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {569--582},
     publisher = {mathdoc},
     volume = {32},
     number = {3},
     year = {2012},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2012_32_3_a14/}
}
TY  - JOUR
AU  - Gerbner, Dániel
AU  - Keszegh, Balázs
AU  - Palmer, Cory
TI  - Generalizations of the tree packing conjecture
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2012
SP  - 569
EP  - 582
VL  - 32
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2012_32_3_a14/
LA  - en
ID  - DMGT_2012_32_3_a14
ER  - 
%0 Journal Article
%A Gerbner, Dániel
%A Keszegh, Balázs
%A Palmer, Cory
%T Generalizations of the tree packing conjecture
%J Discussiones Mathematicae. Graph Theory
%D 2012
%P 569-582
%V 32
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2012_32_3_a14/
%G en
%F DMGT_2012_32_3_a14
Gerbner, Dániel; Keszegh, Balázs; Palmer, Cory. Generalizations of the tree packing conjecture. Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 3, pp. 569-582. http://geodesic.mathdoc.fr/item/DMGT_2012_32_3_a14/

[1] B. Bollobás, Some remarks on packing trees, Discrete Math. 46 (1983) 203-204, doi: 10.1016/0012-365X(83)90254-6.

[2] Y. Caro and Y. Roditty, A note on packing trees into complete bipartite graphs and on Fishburn's conjecture, Discrete Math. 82 (1990) 323-326, doi: 10.1016/0012-365X(90)90209-Z.

[3] C.A. Christen and S.M. Selkow, Some perfect coloring properties of graphs, J. Combin. Theory (B) 27 (1979) 49-59, doi: 10.1016/0095-8956(79)90067-4.

[4] E. Dobson, Packing almost stars into the complete graph, J. Graph Theory 25 (1997) 169-172.

[5] E. Dobson, Packing trees into the complete graph, Combin. Probab. Comput. 11(3) (2002) 263-272, doi: 10.1017/S0963548301005077.

[6] E. Dobson, Packing trees of bounded diameter into the complete graph, Australas. J. Combin. 37 (2007) 89-100.

[7] P. Erdös, Extremal problems in graph theory, in: M. Fiedler (Ed.), Theory of Graphs and its Applications (Academic Press, New York, 1965) 29-36.

[8] A. Gyárfás and J. Lehel, Packing trees of different order into Kₙ, in: Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol.I, 463-469, Colloq. Math. Soc. János Bolyai, 18, North-Holland, (Amsterdam-New York, 1978).

[9] A. Hobbs, Packing trees, in: Proceedings of the Twelfth Southeastern Conference on Combinatorics, Graph Theory and Computing, Vol. II (Baton Rouge, La., 1981). Congr. Numer. 33 (1981), 63-73.

[10] A. Hobbs, B. Bourgeois and J. Kasiraj, Packing trees in complete graphs, Discrete Math. 67 (1987) 27-42, doi: 10.1016/0012-365X(87)90164-6.

[11] Y. Roditty, Packing and covering of the complete graph III. On the tree packing conjecture, Sci. Ser. A Math. Sci. (N.S.) 1 (1988) 81-85.

[12] Y. Roditty, personal communication.

[13] R. Yuster, On packing trees into complete bipartite graphs, Discrete Math. 163 (1997) 325-327, doi: 10.1016/S0012-365X(96)00014-3.

[14] S. Zaks and C.L. Liu, Decomposition of graphs into trees, in: Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977), 643–654, Congr. Numer. No. XIX, (Utilitas Math., Winnipeg, Man., 1977).