On the minimum monochromatic or multicolored subgraph partition problems

DOI10.1016/j.tcs.2007.04.033zbMath1124.68079OpenAlexW2026904819MaRDI QIDQ2456352

Xiaoyan Zhang, Xue Liang Li

Publication date: 18 October 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.04.033

zbMATH Keywords

complexitypartitioninapproximabilitymonochromaticmulticolored

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (13)

The rainbow Steiner tree problem ⋮ Two heuristics for the rainbow spanning forest problem ⋮ Heterochromatic tree partition problem in complete tripartite graphs ⋮ The change-base issue for \(\Omega\)-categories ⋮ The limit–colimit coincidence theorem for -categories ⋮ On the complexity of rainbow spanning forest problem ⋮ Heterochromatic tree partition number in complete multipartite graphs ⋮ Partitioning complete graphs by heterochromatic trees ⋮ Good fuzzy preorders on fuzzy power structures ⋮ Rainbow graph splitting ⋮ The rainbow spanning forest problem ⋮ The formal ball model for -categories ⋮ Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Partitioning by monochromatic trees
• Vertex coverings by monochromatic cycles and trees
• Multicolored forests in bipartite decompositions of graphs
• Generalized partitions of graphs
• Partitioning complete bipartite graphs by monochromatic cycles
• Partitioning into graphs with only small components
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Multicoloured Hamilton cycles
• Partitions of graphs into one or two independent sets and cliques
• Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees
• Minimal colorings for properly colored subgraphs
• Complexity of graph partition problems
• The NP-Completeness of Some Edge-Partition Problems
• The complexity for partitioning graphs by monochromatic trees, cycles and paths
• Partitioning complete multipartite graphs by monochromatic trees
• Multicolored trees in complete graphs
• Graph partition problems into cycles and paths
• Graph colourings and partitions

This page was built for publication: On the minimum monochromatic or multicolored subgraph partition problems