Edge-disjoint rainbow spanning trees in complete graphs. (October 2016)

• Record Type: Journal Article
• Authors: Carraher, James M.; Hartke, Stephen G.; Horn, Paul
• Is Part Of: European journal of combinatorics. Volume 57(2016:Oct.)
• Page Start: 71
• Page End: 84
• Publication Date: 2016-10
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2016.04.003
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: Let G be an edge-colored copy of K n, where each color appears on at most n / 2 edges (the edge-coloring is not necessarily proper). A rainbow spanning tree is a spanning tree of G where each edge has a different color. Brualdi and Hollingsworth (1996) conjectured that every properly edge-colored K n ( n ≥ 6 and even) using exactly n − 1 colors has n / 2 edge-disjoint rainbow spanning trees, and they proved there are at least two edge-disjoint rainbow spanning trees. Kaneko et al. (2003) strengthened the conjecture to include any proper edge-coloring of K n, and they proved there are at least three edge-disjoint rainbow spanning trees. Akbari and Alipour (2007) showed that each K n that is edge-colored such that no color appears more than n / 2 times contains at least two rainbow spanning trees. We prove that if n ≥ 1, 000, 000, then an edge-colored K n, where each color appears on at most n / 2 edges, contains at least ⌊ n / ( 1000 log n ) ⌋ edge-disjoint rainbow spanning trees.