Abstract | ||
---|---|---|
The Gyarfas 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. Gyarfas 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. |
Year | DOI | Venue |
---|---|---|
2012 | 10.7151/dmgt.1628 | DISCUSSIONES MATHEMATICAE GRAPH THEORY |
Keywords | Field | DocType |
packing,tree packing | Complete graph,Graph,Discrete mathematics,Combinatorics,Vertex (geometry),Generalization,Set packing,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
32 | 3 | 1234-3099 |
Citations | PageRank | References |
3 | 0.57 | 7 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Dániel Gerbner | 1 | 46 | 21.61 |
Balázs Keszegh | 2 | 156 | 24.36 |
Cory Palmer | 3 | 44 | 10.33 |