2016/05/15 by Hung‐Lin Fu, Fu, Hung-Lin, Yuan–Hsun Lo +5
Computer Science · Mathematics · #05C05 #05C15 #05C70 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1605.04501
openalex publication_date 2016/05/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A spanning tree of a properly edge-colored complete graph, Kn, is rainbow provided that each of its edges receives a distinct color. In 1996, Brualdi and Hollingsworth conjectured that if K2m is properly (2m-1)-edge-colored, then the edges of K2m can be partitioned into m rainbow spanning trees except when m=2. By means of an explicit, constructive approach, in this paper we construct \lfloor √(6m+9)/3 \rfloor mutually edge-disjoint rainbow spanning trees for any positive value of m. Not only are the rainbow trees produced, but also some structure of each rainbow spanning tree is determined in the process. This improves upon best constructive result to date in the literature which produces exactly three rainbow trees.