Download PDF - Generalizations of the tree packing conjectureAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Generalizations of the tree packing conjecture

Authors 1, 1, 2, 1

Affiliations

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

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

ENG
packing, tree packing

Bibliography

  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 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.
  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).
Discussiones Mathematicae Graph Theory
2012/32/3
Export to PBN, Opens in new tab
Pages:
569-582
Main language of publication
English
Received
2010-11-10
Accepted
2011-08-11
Published
2012

DOI: 10.7151/dmgt.1628

Exact and natural sciences