Generalized partitions of graphs

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

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.

Recommendations

Cites work

Cited in

(32)

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)