Nearly optimal packings of equally sized rainbow forests
En palabras de los autores
A forest in an edge-colored graph is rainbow if its edges have pairwise distinct colors. We prove that, for every fixed , every properly edge-colored simple graph with edges and color classes of size at most contains at least pairwise edge-disjoint rainbow forests, each with exactly edges, uniformly for as . This establishes the packing conclusion in the -edge formulation of a conjecture of Montgomery, Pokrovskiy, and Sudakov throughout this range, with the original global color bound. The number of forests is asymptotically optimal, and the leading constant in the range of is best possible. The proof combines random star forests with a matching theorem for bipartite hypergraphs.
Apareció: viernes, 25 de septiembre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 7 pages