Journal of Graph Theory · 2006 · 32 citations · 12 references
Natural SciencesHigh-performance ComputingCombinatoricsGraph ColoringGraph TheoryTree AlgorithmsTree-graph
Abstract A multicolored tree is a tree whose edges have different colors. Brualdi and Hollingsworth 5 proved in any proper edge coloring of the complete graph K 2 n ( n > 2) with 2 n − 1 colors, there are two edge‐disjoint multicolored spanning trees. In this paper we generalize this result showing that if ( a 1 ,…, a k ) is a color distribution for the complete graph K n , n ≥ 5, such that $2 \leq a_{1} \leq a_{2} \leq \cdots \leq a_{k} \leq (n+ 1)/ 2$ , then there exist two edge‐disjoint multicolored spanning trees. Moreover, we prove that for any edge coloring of the complete graph K n with the above distribution if T is a non‐star multicolored spanning tree of K n , then there exists a multicolored spanning tree T ' of K n such that T and T ' are edge‐disjoint. Also it is shown that if K n , n ≥ 6, is edge colored with k colors and $k \geq {{{n}-{2}} \choose {2}}+{3}$ , then there exist two edge‐disjoint multicolored spanning trees. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 221–232, 2007
12
J. Fields · 2001 · 4.1K citations
Colorings and orientations of graphs
Noga Alon, Michael Tarsi · COMBINATORICA · 1992 · 514 citations
J W Essam · Bulletin of the London Mathematical Society · 1976 · 102 citations
Edge-Colorings with No Large Polychromatic Stars
Tao Jiang · Graphs and Combinatorics · 2002 · 61 citations