# Generalizations of the tree packing conjecture

Dániel Gerbner; Balázs Keszegh; Cory Palmer

Discussiones Mathematicae Graph Theory (2012)

- Volume: 32, Issue: 3, page 569-582
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topDániel Gerbner, Balázs Keszegh, and Cory Palmer. "Generalizations of the tree packing conjecture." Discussiones Mathematicae Graph Theory 32.3 (2012): 569-582. <http://eudml.org/doc/270979>.

@article{DánielGerbner2012,

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.},

author = {Dániel Gerbner, Balázs Keszegh, Cory Palmer},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {packing; tree packing},

language = {eng},

number = {3},

pages = {569-582},

title = {Generalizations of the tree packing conjecture},

url = {http://eudml.org/doc/270979},

volume = {32},

year = {2012},

}

TY - JOUR

AU - Dániel Gerbner

AU - Balázs Keszegh

AU - Cory Palmer

TI - Generalizations of the tree packing conjecture

JO - Discussiones Mathematicae Graph Theory

PY - 2012

VL - 32

IS - 3

SP - 569

EP - 582

AB - 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.

LA - eng

KW - packing; tree packing

UR - http://eudml.org/doc/270979

ER -

## References

top- [1] B. Bollobás, Some remarks on packing trees, Discrete Math. 46 (1983) 203-204, doi: 10.1016/0012-365X(83)90254-6. Zbl0509.05058
- [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. Zbl0702.05027
- [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. Zbl0427.05033
- [4] E. Dobson, Packing almost stars into the complete graph, J. Graph Theory 25 (1997) 169-172. Zbl0884.05070
- [5] E. Dobson, Packing trees into the complete graph, Combin. Probab. Comput. 11(3) (2002) 263-272, doi: 10.1017/S0963548301005077. Zbl1032.05112
- [6] E. Dobson, Packing trees of bounded diameter into the complete graph, Australas. J. Combin. 37 (2007) 89-100. Zbl1121.05030
- [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. Zbl0487.05056
- [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. Zbl0642.05043
- [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. Zbl0699.05044
- [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. Zbl0871.05013
- [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). Zbl0402.05052

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.