PDF
Discussiones Mathematicae Graph Theory 32(3) (2012)
569-582
DOI: https://doi.org/10.7151/dmgt.1628
Generalizations of the Tree Packing Conjecture
| Dániel Gerbnera, Balázs Keszegh ab and Cory Palmera
a Hungarian Academy of Sciences, |
Abstract
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
2010 Mathematics Subject Classification: 05C70, 05C05.
References
| [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 Kn, 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). |
Received 10 November 2010
Revised 11 August 2011
Accepted 1 October 2011
Close