Multicolored trees in complete graphs

✍ Scribed by S. Akbari; A. Alipour

• Publisher: John Wiley and Sons
• Year: 2007
• Tongue: English
• Weight: 163 KB
• Volume: 54
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20204

✦ Synopsis

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