2023/10/30 by Asthana, Anant, Shreev Goyal, Goyal, Shreev
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2310.19242
openalex publication_date 2023/10/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a connected multigraph with n vertices, and suppose G has been edge-colored with n-1 colors so that each color class induces a spanning tree. Rota's Basis Conjecture for graphic matroids posits that one can find n-1 mutually edge-disjoint rainbow spanning trees. In a recent paper, Maezawa and Yazawa have shown that the conjecture holds if one assumes that the color classes induce spanning stars. We delve further into the star case to explore some extreme subcases including: all stars with different centers, the same center, or one of two centers. In addition, we identify the cases in which a graph composed of monochromatic stars can be decomposed into rainbow stars. We also show that the statement is false if one replaces `stars' with `paths'.