HackerPapers

arXiv:1104.0642math.CO

Generalizations of the Tree Packing Conjecture

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

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

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.

arXiv comments
Journal reference
DOI
Subjects
math.COCombinatorics

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Mar 2020 to Mar 2020.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. An unsolved problem in graph theory 1 comment

    • I, uh, wasted a bit of time once on the Tree Packing conjecture of Gyarfas: https://arxiv.org/abs/1104.0642 In your left hand, place a complete graph, which has n-choose-2 edges. In your right hand, a collection of trees on 2, 3, 4, ..., n-1 vertices, which, by miraculous…

      sdenton4View on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.