PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2012 | 32 | 3 | 569-582
Tytuł artykułu

Generalizations of the tree packing conjecture

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Słowa kluczowe
Wydawca
Rocznik
Tom
32
Numer
3
Strony
569-582
Opis fizyczny
Daty
wydano
2012
otrzymano
2010-11-10
poprawiono
2011-08-11
zaakceptowano
2011-10-01
Twórcy
  • Hungarian Academy of Sciences, Alfréd Rényi Institute of Mathematics, P.O.B. 127, Budapest H-1364, Hungary
  • Hungarian Academy of Sciences, Alfréd Rényi Institute of Mathematics, P.O.B. 127, Budapest H-1364, Hungary
  • Ecole Polytechnique Fédérale de Lausanne, EPFL-SB-IMB-DCG, 1015 Lausanne, Switzerland
autor
  • Hungarian Academy of Sciences, Alfréd Rényi Institute of Mathematics, P.O.B. 127, Budapest H-1364, Hungary
Bibliografia
  • [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).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1628
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.