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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1628,
author = {D\'aniel Gerbner and Bal\'azs Keszegh and Cory Palmer},
title = {Generalizations of the tree packing conjecture},
journal = {Discussiones Mathematicae Graph Theory},
volume = {32},
year = {2012},
pages = {569-582},
zbl = {1257.05129},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1628}
}
Dániel Gerbner; Balázs Keszegh; Cory Palmer. Generalizations of the tree packing conjecture. Discussiones Mathematicae Graph Theory, Tome 32 (2012) pp. 569-582. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1628/
[000] [1] B. Bollobás, Some remarks on packing trees, Discrete Math. 46 (1983) 203-204, doi: 10.1016/0012-365X(83)90254-6. | Zbl 0509.05058
[001] [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. | Zbl 0702.05027
[002] [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. | Zbl 0427.05033
[003] [4] E. Dobson, Packing almost stars into the complete graph, J. Graph Theory 25 (1997) 169-172. | Zbl 0884.05070
[004] [5] E. Dobson, Packing trees into the complete graph, Combin. Probab. Comput. 11(3) (2002) 263-272, doi: 10.1017/S0963548301005077. | Zbl 1032.05112
[005] [6] E. Dobson, Packing trees of bounded diameter into the complete graph, Australas. J. Combin. 37 (2007) 89-100. | Zbl 1121.05030
[006] [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.
[007] [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).
[008] [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. | Zbl 0487.05056
[009] [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. | Zbl 0642.05043
[010] [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. | Zbl 0699.05044
[011] [12] Y. Roditty, personal communication.
[012] [13] R. Yuster, On packing trees into complete bipartite graphs, Discrete Math. 163 (1997) 325-327, doi: 10.1016/S0012-365X(96)00014-3. | Zbl 0871.05013
[013] [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). | Zbl 0402.05052