Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-28T17:27:01.789Z Has data issue: false hasContentIssue false
  • English
  • Français

Proof of a Packing Conjecture of Bollobás

Published online by Cambridge University Press:  12 September 2008

János Komlós ,
Gábor N. Sárközy  and
Endre Szemerédi
János Komlós
Affiliation:
Rutgers University, USAHungarian Academy of Sciences, Hungary
Gábor N. Sárközy
Affiliation:
Rutgers University, USAHungarian Academy of Sciences, Hungary
Endre Szemerédi
Affiliation:
Rutgers University, USAHungarian Academy of Sciences, Hungary
Get access Rights & Permissions [Opens in a new window]

Abstract

Béla Bollobás [1] conjectured the following. For any positive integer Δ and real 0 < c < ½ there exists an n0 with the following properties. If n ≥ n0, T is a tree of order n and maximum degree Δ, and G is a graph of order n and maximum degree not exceeding cn, then there is a packing of T and G. Here we prove this conjecture. Auxiliary Theorem 2.1 is of independent interest.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 4 , Issue 3 , September 1995 , pp. 241 - 255
Copyright
Copyright © Cambridge University Press 1995

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Bollobás, B. (1978) Extremal Graph Theory, Academic Press, London.Google Scholar
[2]Bollobás, B. and Eldridge, S. E. (1978) Packings of graphs and applications to computational complexity. J. Combinatorial Theory (B) 25 105–124.CrossRefGoogle Scholar
[3]Broder, A., Frieze, A. and Upfal, E. (1992) Existence and construction of edge disjoint paths on expander graphs. Proc. 24th STOC, Victoria, BC, Canada, pp. 140–149.Google Scholar
[4]Hajnal, A. and Szemerédi, E. (1970) Proof of a conjecture of Erdős. In Combinatorial Theory and its Applications: Vol. II (Erdős, P., Rényi, A. and Sós, V.T. eds.), Colloq. Math. Soc. J. Bolyai 4, North-Holland, Amsterdam, pp. 601–623.Google Scholar
[5]Komlós, J. and Sós, V. (1991) Regular subgraphs of graphs. Manuscript.Google Scholar
[6]Lovász, L. (1979) Combinatorial Problems and Exercises. Akadémiai Kiadó, Budapest.Google Scholar
[7]Sauer, N. and Spencer, J. (1978) Edge disjoint placement of graphs. J. Combinatorial Theory (B) 25 295–302.CrossRefGoogle Scholar
[8]Szemerédi, E. (1976) Regular partitions of graphs. Colloques Internationaux C.N.R.S. No. 260 – Problèmes Combinatoires et Théorie des Graphes, Orsay, France, pp. 399–401.Google Scholar
[9]Szemerédi, E. (1975) On a set containing no k elements in arithmetic progression. Acta Arithmetica XXVII 199–245.CrossRefGoogle Scholar