Generalized partitions of graphs
type: Item
instance of: scholarly article
title: Generalized partitions of graphs
zbMATH Open document ID: 0917.05056
DOI: 10.1016/S0166-218X(98)00124-3
author: Gary MacGillivray
author: Min-Li Yu
published in: Discrete Applied Mathematics
publication date: 1999-07-18T00:00:00Z
review text: The authors introduce a general graph partitioning problem: Let \(C\) be a class of graphs and \(H\) a fixed graph with vertex class \(V(H)=\{1,2,\dots,n\}\). An (resp. ONTO) \((H,C)\)-partition of a graph \(G\) is a partition \(V_1,V_2,\dots,V_n\) of \(V(G)\) such that, for each \(i\), the subgraph of \(G\) induced by \(V_i\) belongs to \(C\) and, if \(i\neq j\in V(H)\), there is an edge with one end in \(V_i\) and the other in \(V_j\) (resp. if and only if \(ij\in E(H)\)). Let \(K\) be the class of all complete graphs including the empty graph, \(K'\) the class of all complete graphs excluding the empty graph with the class of vertices being empty. Let \(B\) be the class of all complete bipartite graphs with at least one edge, together with \(K_0\) and \(K_1\). \(S\) is the class of all stars. A prime denotes the same class of graphs, excluding the empty graph. It is proved that if \(H\) is a triangle-free graph, then the \((H,K)\)-partitions, \((H,K')\)-partitions, ONTO \((H,K')\)-partitions, \((H,B)\)-partitions, \((H,B')\)-partitions, ONTO \((H,B')\)-partitions, \((H,S)\)-partitions, \((H,S')\)-partitions, and ONTO \((H,S')\)-partitions are polynomial. If \(K_3\) is a subgraph of \(H\), then the \((H,K)\)-partitions, \((H,K')\)-partitions, ONTO \((H,K')\)-partitions, \((H,B)\)-partitions, \((H,B')\)-partitions, ONTO \((H,B')\)-partitions, \((H,S)\)-partitions, \((H,S')\)-partitions, and ONTO \((H,S')\)-partitions are NP-complete.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1271070
zbMATH Keywords: conditional coloring
zbMATH Keywords: 2-sat
zbMATH Keywords: complexity
zbMATH Keywords: algorithm
zbMATH Keywords: NP-complete
zbMATH Keywords: graph partitioning
reviewed by: Guojun Li
MaRDI profile type: Publication
cites work: Q3688407
cites work: Contractibility and NP-completeness
cites work: On generalized graph colorings
cites work: Packing subgraphs in a graph
cites work: A matching problem with side conditions
cites work: Q3760563
cites work: On the Complexity of Timetable and Multicommodity Flow Problems
cites work: Q4198056
cites work: Q3220612
cites work: On the completeness of a generalized matching problem
cites work: On generalized matching problems
cites work: On the Complexity of General Graph Factor Problems
cites work: Packings by cliques and by finite families of graphs
cites work: Packings by Complete Bipartite Graphs
cites work: On Restricted Two-Factors
cites work: On the complexity of H-coloring
cites work: On the Computational Complexity of Combinatorial Problems
full work available at URL: s0166-218x(98)00124-3
OpenAlex ID: W2149498497
Wikidata QID: Q126440158
description: scientific article; zbMATH DE number 1271070