Discussiones Mathematicae Graph Theory 32(3) (2012) 569-582
doi: 10.7151/dmgt.1628

[BIBTex] [PDF] [PS]

Generalizations of the Tree Packing Conjecture

Dániel Gerbnera, Balázs Keszegh ab and Cory Palmera

a Hungarian Academy of Sciences,
Alfréd Rényi Institute of Mathematics,
P.O.B. 127, Budapest H-1364, Hungary
b Ecole Polytechnique Fédérale de Lausanne
EPFL-SB-IMB-DCG, 1015 Lausanne, Switzerland


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.


[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