Partitioning complete graphs by heterochromatic trees

DOI10.1007/S10255-012-0177-ZMaRDI QIDQ692699zbMATH OpenOpenAlexFDO

Authors Zemin Jin, Xueliang Li

Publication date 6 December 2012

Published in Acta Mathematicae Applicatae Sinica. English Series (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0711.2849

zbMATH Keywords

edge-colored graphheterochromatic treepartition

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

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.

Recommendations

• Heterochromatic tree partition number in complete multipartite graphs
• Heterochromatic tree partition problem in complete tripartite graphs
• Heterochromatic tree partition numbers for complete bipartite graphs
• Partitioning complete multipartite graphs by monochromatic trees
• On tree-partitions of graphs
• Monochromatic tree partition for complete multipartite graphs
• Partitions of Graphs into Trees
• Complete partitions of graphs
• Complete partitions of graphs
• Partitioning graphs of bounded tree-width

Cites work

• An improved bound for the monochromatic cycle partition number
• Heterochromatic tree partition numbers for complete bipartite graphs
• scientific article; zbMATH DE number 15152 (Why is no real title available?)
• Monochromatic Paths in Graphs
• On the minimum monochromatic or multicolored subgraph partition problems
• Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees
• Partitioning by monochromatic trees
• Partitioning complete bipartite graphs by monochromatic cycles
• Partitioning complete multipartite graphs by monochromatic trees
• Partitioning Two-Coloured Complete Graphs into Two Monochromatic Cycles
• Vertex coverings by monochromatic cycles and trees
• Vertex coverings by monochromatic paths and cycles

Cited in

(6)

• Heterochromatic tree partition number in complete multipartite graphs
• A generalization of heterochromatic graphs and \(f\)-chromatic spanning forests
• Heterochromatic tree partition problem in complete tripartite graphs
• Partitioning complete multipartite graphs by monochromatic trees
• On heterochromatic out-directed spanning trees in tournaments
• Heterochromatic tree partition numbers for complete bipartite graphs

This page was built for publication: Partitioning complete graphs by heterochromatic trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q692699)