On the minimum monochromatic or multicolored subgraph partition problems

DOI10.1016/J.TCS.2007.04.033MaRDI QIDQ2456352zbMATH OpenOpenAlexFDO

Authors Xiaoyan Zhang, Xueliang 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

complexityinapproximabilitymonochromaticmulticoloredpartition

Mathematics Subject Classification ID

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

Recommendations

• The complexity for partitioning graphs by monochromatic trees, cycles and paths
• Vertex partitions of \(r\)-edge-colored graphs
• On the complexity of edge-colored subgraph partitioning problems in network optimization
• Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey
• Approximation algorithms for the minimum rainbow subgraph problem

Cites work

• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Complexity of graph partition problems
• Generalized partitions of graphs
• Graph colourings and partitions
• Graph partition problems into cycles and paths
• scientific article; zbMATH DE number 434896 (Why is no real title available?)
• scientific article; zbMATH DE number 3558962 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256748 (Why is no real title available?)
• scientific article; zbMATH DE number 2147947 (Why is no real title available?)
• Minimal colorings for properly colored subgraphs
• Multicolored forests in bipartite decompositions of graphs
• Multicolored trees in complete graphs
• Multicoloured Hamilton cycles
• 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 into graphs with only small components
• Partitions of graphs into one or two independent sets and cliques
• The complexity for partitioning graphs by monochromatic trees, cycles and paths
• The NP-Completeness of Some Edge-Partition Problems
• Vertex coverings by monochromatic cycles and trees

Cited in

(16)

• Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey
• On the complexity of rainbow spanning forest problem
• The rainbow spanning forest problem
• Two heuristics for the rainbow spanning forest problem
• Heterochromatic tree partition number in complete multipartite graphs
• The rainbow Steiner tree problem
• On the complexity of edge-colored subgraph partitioning problems in network optimization
• The formal ball model for \(\mathcal Q\)-categories
• Submodular potential function for the minimum color spanning tree problem of edge-colored graphs
• The limit–colimit coincidence theorem for -categories
• Heterochromatic tree partition problem in complete tripartite graphs
• On the approximation of Min Split-coloring and Min Cocoloring
• Partitioning complete graphs by heterochromatic trees
• Rainbow graph splitting
• The change-base issue for \(\Omega\)-categories
• Good fuzzy preorders on fuzzy power structures

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

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