On the minimum monochromatic or multicolored subgraph partition problems
From MaRDI portal
Publication:2456352
DOI10.1016/j.tcs.2007.04.033zbMath1124.68079MaRDI QIDQ2456352
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
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Related Items
Heterochromatic tree partition problem in complete tripartite graphs, Partitioning complete graphs by heterochromatic trees, Rainbow graph splitting, The change-base issue for \(\Omega\)-categories, Good fuzzy preorders on fuzzy power structures, 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 formal ball model for -categories, The limit–colimit coincidence theorem for -categories
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
