Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees

DOI10.1007/S10878-006-8460-7MaRDI QIDQ2479574zbMATH OpenOpenAlexFDO

Authors Bing Wei, Zemin Jin, Mikio Kano, Xueliang Li

Publication date 4 April 2008

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-006-8460-7

zbMATH Keywords

complete multipartite graphscomplexitygraph partitioningmonochromatic subgraphs

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Programming involving graphs or networks (90C35)

Recommendations

• Vertex partitions of \(r\)-edge-colored graphs
• The complexity for partitioning graphs by monochromatic trees, cycles and paths
• Packing problems in edge-colored graphs

Cites work

• Clique partitions, graph compression and speeding-up algorithms
• Complexity of graph partition problems
• Generalized partitions of graphs
• Graph partition problems into cycles and paths
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• Partitioning by monochromatic trees
• Partitioning complete bipartite graphs by monochromatic cycles
• Partitioning complete multipartite graphs by monochromatic trees
• 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
• Vertex coverings by monochromatic paths and cycles
• Vertex partitions of \(r\)-edge-colored graphs

Cited in

(11)

• Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey
• Packing problems in edge-colored graphs
• Almost partitioning 2-edge-colourings of 3-uniform hypergraphs with two monochromatic tight cycles
• Partitioning edge-coloured infinite complete bipartite graphs into monochromatic paths
• Heterochromatic tree partition number in complete multipartite graphs
• An efficiently solvable graph partition problem to which many problems are reducible
• On the minimum monochromatic or multicolored subgraph partition problems
• Heterochromatic tree partition problem in complete tripartite graphs
• The complexity for partitioning graphs by monochromatic trees, cycles and paths
• Partitioning complete graphs by heterochromatic trees
• Vertex partitions of \(r\)-edge-colored graphs

This page was built for publication: Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees

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