Vertex partitions of \(r\)-edge-colored graphs

DOI10.1007/S11766-008-0117-0zbMath1150.05008OpenAlexW2089122992MaRDI QIDQ933003

Ze-min Jin, Xue Liang Li

Publication date: 6 August 2008

Published in: Applied Mathematics. Series B (English Edition) (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11766-008-0117-0

zbMATH Keywords

linear time algorithmNP-completemonochromatic tree

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Applications of graph theory to circuits and networks (94C15)

Related Items (2)

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

• Linear algorithm for optimal path cover problem on interval graphs
• Partitioning by monochromatic trees
• Vertex coverings by monochromatic cycles and trees
• Optimal chain partitions of trees
• Minimum node disjoint path covering for circular-arc graphs
• Optimal path cover problem on block graphs and bipartite permutation graphs
• The path-partition problem in block graphs
• Partitioning complete bipartite graphs by monochromatic cycles
• Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees
• The complexity for partitioning graphs by monochromatic trees, cycles and paths
• 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: Vertex partitions of \(r\)-edge-colored graphs