Many edge-disjoint rainbow spanning trees in general graphs

Abstract

A rainbow spanning tree in an edge-colored graph is a spanning tree in which each edge is a different color. Carraher, Hartke, and Horn showed that for $n$ and $C$ large enough, if $G$ is an edge-colored copy of $K_n$ in which each color class has size at most $n/2$, then $G$ has at least $\lfloor n/(C\log n)\rfloor$ edge-disjoint rainbow spanning trees. Here we strengthen this result by showing that if $G$ is any edge-colored graph with $n$ vertices in which each color appears on at most $\delta \cdot {\lambda }_1/2$ edges, where $\delta \ge C\log n$ for $n$ and $C$ sufficiently large and ${\lambda }_1$ is the second-smallest eigenvalue of the normalized Laplacian matrix of $G$, then $G$ contains at least $\lfloor \frac{\delta \cdot {\lambda }_1}{C\log n}\rfloor$ edge-disjoint rainbow spanning trees.

References in corpus (2)

• Size biased couplings and the spectral gap for random regular graphs
• On the Number of Rainbow Spanning Trees in Edge-Colored Complete Graphs

Cited by in corpus (1)

• An Extremal Problem on Rainbow Spanning Trees in Graphs