Generalized partitions of graphs

DOI10.1016/S0166-218X(98)00124-3zbMath0917.05056OpenAlexW2149498497WikidataQ126440158 ScholiaQ126440158MaRDI QIDQ1283792

Min-Li Yu, Gary MacGillivray

Publication date: 18 July 1999

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(98)00124-3

zbMATH Keywords

complexityalgorithmgraph partitioningNP-completeconditional coloring2-sat

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Packing $k$-Matchings and $k$-Critical Graphs ⋮ On the minimum monochromatic or multicolored subgraph partition problems ⋮ The complexity for partitioning graphs by monochromatic trees, cycles and paths ⋮ Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees

Cites Work

• Packings by cliques and by finite families of graphs
• On the complexity of H-coloring
• A matching problem with side conditions
• On generalized matching problems
• Packing subgraphs in a graph
• On the Complexity of General Graph Factor Problems
• Packings by Complete Bipartite Graphs
• Contractibility and NP-completeness
• On generalized graph colorings
• On Restricted Two-Factors
• On the Computational Complexity of Combinatorial Problems
• On the Complexity of Timetable and Multicommodity Flow Problems
• On the completeness of a generalized matching problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Generalized partitions of graphs