Generalized partitions of graphs (Q1283792): Difference between revisions

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.