2011/04/04 by Dániel Gerbner, Gerbner, Dániel, Balázs Keszegh +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1104.0642
openalex publication_date 2011/04/04 · arxiv created 2011/10/21 · arxiv updated 2011/10/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.