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

Abstract

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

How to cite

top

Dá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. [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. [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. [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. [4] E. Dobson, Packing almost stars into the complete graph, J. Graph Theory 25 (1997) 169-172. Zbl0884.05070
  5. [5] E. Dobson, Packing trees into the complete graph, Combin. Probab. Comput. 11(3) (2002) 263-272, doi: 10.1017/S0963548301005077. Zbl1032.05112
  6. [6] E. Dobson, Packing trees of bounded diameter into the complete graph, Australas. J. Combin. 37 (2007) 89-100. Zbl1121.05030
  7. [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. [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. [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. [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. [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. [12] Y. Roditty, personal communication. 
  13. [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. [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

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.