Multicolored trees in complete graphs |
| |
| Authors: | S Akbari A Alipour |
| |
| Institution: | 1. Department of Mathematical Sciences, Sharif University of Technology, P.O. Box 11365‐9415, Tehran, Iran;2. The institute for Studies in Theoretical Physics and Mathematics (IPM), Tehran, Iran;3. AMS (2000) Subject Classification : 05B35, 05C05, 05C15, 05D15. |
| |
| 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 K2n(n > 2) with 2n ? 1 colors, there are two edge‐disjoint multicolored spanning trees. In this paper we generalize this result showing that if (a1,…, ak) is a color distribution for the complete graph Kn, n ≥ 5, such that  , then there exist two edge‐disjoint multicolored spanning trees. Moreover, we prove that for any edge coloring of the complete graph Kn with the above distribution if T is a non‐star multicolored spanning tree of Kn, then there exists a multicolored spanning tree T' of Kn such that T and T' are edge‐disjoint. Also it is shown that if Kn, n ≥ 6, is edge colored with k colors and  , then there exist two edge‐disjoint multicolored spanning trees. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 221–232, 2007 |
| |
| Keywords: | Multicolored tree Rado's Theorem complete graph |
|
|
