The complexity for partitioning graphs by monochromatic trees, cycles and paths

DOI10.1080/00207160412331290685zbMath1078.05021OpenAlexW2034740402MaRDI QIDQ4652867

Ze-min Jin, Xue Liang Li

Publication date: 28 February 2005

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207160412331290685

zbMATH Keywords

computational complexitycombinatorial problemapproximation algorithmvertex disjoint

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15)

Related Items (4)

Vertex partitions of \(r\)-edge-colored graphs ⋮ On the minimum monochromatic or multicolored subgraph partition problems ⋮ Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees ⋮ Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey

Cites Work

• Partitioning by monochromatic trees
• Vertex coverings by monochromatic cycles and trees
• Generalized partitions of graphs
• Partitioning complete bipartite graphs by monochromatic cycles
• The minimum labeling spanning trees
• Clique partitions, graph compression and speeding-up algorithms
• Partitions of graphs into one or two independent sets and cliques
• A threshold of ln n for approximating set cover
• The NP-Completeness of Some Edge-Partition Problems
• Spanning trees with many or few colors in edge-colored graphs
• Partitioning complete multipartite graphs by monochromatic trees
• Vertex coverings by monochromatic paths and cycles
• Graph partition problems into cycles and paths

This page was built for publication: The complexity for partitioning graphs by monochromatic trees, cycles and paths