Special Case of Rota's Basis Conjecture on Graphic Matroids

  • Shun-ichi Maezawa
  • Akiko Yazawa


Gian-Carlo Rota conjectured that for any $n$ bases $B_1,B_2,\ldots,B_n$ in a matroid of rank $n$, there exist $n$ disjoint transversal bases of $B_1,B_2,\ldots,B_n$. The conjecture for graphic matroids corresponds to the problem of an edge-decomposition as follows; If an edge-colored connected multigraph $G$ has $n-1$ colors and the graph induced by the edges colored with $c$ is a spanning tree for each color $c$, then $G$ has $n-1$ mutually edge-disjoint rainbow spanning trees. In this paper, we prove that edge-colored graphs where the edges colored with $c$ induce a spanning star for each color $c$ can be decomposed into rainbow spanning trees.

Article Number