Generalized partitions of graphs

DOI10.1016/S0166-218X(98)00124-3MaRDI QIDQ1283792zbMATH OpenOpenAlexWikidataFDO

Authors Gary MacGillivray, Min-Li Yu

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

algorithmcomplexitygraph partitioningNP-completeconditional coloring2-sat

Mathematics Subject Classification ID

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

Recommendations

• On the complexity of partitioning graphs into connected subgraphs
• The Complexity of the List Partition Problem for Graphs
• The list partition problem for graphs
• scientific article; zbMATH DE number 3963195
• Partitioning a graph into disjoint cliques and a triangle-free graph

Cites work

• scientific article; zbMATH DE number 3885934 (Why is no real title available?)
• scientific article; zbMATH DE number 3910413 (Why is no real title available?)
• scientific article; zbMATH DE number 4010539 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A matching problem with side conditions
• Contractibility and NP-completeness
• On Restricted Two-Factors
• On generalized graph colorings
• On generalized matching problems
• On the Complexity of General Graph Factor Problems
• On the Complexity of Timetable and Multicommodity Flow Problems
• On the Computational Complexity of Combinatorial Problems
• On the completeness of a generalized matching problem
• On the complexity of H-coloring
• Packing subgraphs in a graph
• Packings by Complete Bipartite Graphs
• Packings by cliques and by finite families of graphs

Cited in

(29)

• NP-hard and linear variants of hypergraph partitioning
• A polynomial characterization of some graph partitioning problems
• scientific article; zbMATH DE number 2227473 (Why is no real title available?)
• Vertex set partitions preserving conservativeness
• On a graph partition problem with application to VLSI layout
• Graph-Theoretic Concepts in Computer Science
• More aspects of arbitrarily partitionable graphs
• Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees
• The list partition problem for graphs
• Partitions of large Rado graphs
• Partitions of Graphs
• General introduction to graph partitioning
• FindingH-partitions efficiently
• Solving partition problems almost always requires pushing many vertices around
• A Partially Ordered Structure and a Generalization of the Canonical Partition for General Graphs with Perfect Matchings
• Complexity of conditional colourings with given template
• The complexity for partitioning graphs by monochromatic trees, cycles and paths
• Computational aspects of greedy partitioning of graphs
• The Complexity of the List Partition Problem for Graphs
• Packing $k$-Matchings and $k$-Critical Graphs
• Partitioning a graph into disjoint cliques and a triangle-free graph
• scientific article; zbMATH DE number 3872703 (Why is no real title available?)
• scientific article; zbMATH DE number 3963195 (Why is no real title available?)
• The complexity of partitioning into disjoint cliques and a triangle-free graph
• On the complexity of partitioning a graph into a few connected subgraphs
• Krausz dimension and its generalizations in special graph classes
• Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard
• scientific article; zbMATH DE number 3889586 (Why is no real title available?)
• On the minimum monochromatic or multicolored subgraph partition problems

This page was built for publication: Generalized partitions of graphs

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