Partitioning complete graphs by heterochromatic trees

2007/11/19 by Zemin Jin, Xueliang Li, Jin, Zemin +1
Mathematics · #05C05 #05C15 #05C70 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C05 #msc:05C15 #msc:05C70

paper · pdf · doi:10.48550/arxiv.0711.2849

7 pages

arxiv created 2007/11/19 · arxiv updated 2009/12/01

Abstract

A \it heterochromatic tree is an edge-colored tree in which any two edges have different colors. The \it heterochromatic tree partition number of an r-edge-colored graph G, denoted by t_r(G), is the minimum positive integer p such that whenever the edges of the graph G are colored with r colors, the vertices of G can be covered by at most p vertex-disjoint heterochromatic trees. In this paper we determine the heterochromatic tree partition number of an r-edge-colored complete graph.

Related

• Partitioning 3-edge-colored complete equi-bipartite graphs by monochromatic trees under a color degree condition
• Heterochromatic tree partition number of a complete multipartite graph
• On the number of heterochromatic trees in nice and beautiful colourings of complete graphs
• Partitioning a graph into monochromatic connected subgraphs
• The absence of monochromatic triangle implies various properly colored spanning trees