Generalizations of the tree packing conjecture

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

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish
Pages (from-to)569-582
Number of pages14
JournalDiscussiones Mathematicae - Graph Theory
Volume32
Issue number3
DOIs
StatePublished - 2012

Keywords

  • Packing
  • Tree packing

Fingerprint

Dive into the research topics of 'Generalizations of the tree packing conjecture'. Together they form a unique fingerprint.

Cite this