The \(K_r\)-packing problem.

*(English)*Zbl 0978.05060Summary: For a fixed integer \(r\geq 2\), the \(K_r\)-packing problem is to find the maximum number of pairwise vertex-disjoint \(K_r\)’s (complete graphs on \(r\) vertices) in a given graph. The \(K_r\)-factor problem asks for the existence of a partition of the vertex set of a graph into \(K_r\)’s. The \(K_r\)-packing problem is a natural generalization of the classical matching problem, but turns out to be much harder for \(r\geq 3\)—it is known that for \(r\geq 3\) the \(K_r\)-factor problem is NP-complete for graphs with clique number \(r\). This paper considers the complexity of the \(K_r\)-packing problem on restricted classes of graphs.

We first prove that for \(r\geq 3\) the \(K_r\)-packing problem is NP-complete even when restrict to chordal graphs, planar graphs (for \(r= 3, 4\) only), line graphs and total graphs. The hardness result for \(K_3\)-packing on chordal graphs answers an open question raised in [E. Dahlhaus and M. Karpinski, Discrete Appl. Math. 84, No. 1-3, 79-91 (1998; Zbl 0902.68146)]. We also give (simple) polynomial algorithms for the \(K_3\)-packing and the \(K_r\)-factor problems on split graphs (this is interesting in light of the fact the \(K_r\)-packing becomes NP-complete on split graphs for \(r\geq 4\)), and for the \(K_r\)-packing problem on cographs.

We first prove that for \(r\geq 3\) the \(K_r\)-packing problem is NP-complete even when restrict to chordal graphs, planar graphs (for \(r= 3, 4\) only), line graphs and total graphs. The hardness result for \(K_3\)-packing on chordal graphs answers an open question raised in [E. Dahlhaus and M. Karpinski, Discrete Appl. Math. 84, No. 1-3, 79-91 (1998; Zbl 0902.68146)]. We also give (simple) polynomial algorithms for the \(K_3\)-packing and the \(K_r\)-factor problems on split graphs (this is interesting in light of the fact the \(K_r\)-packing becomes NP-complete on split graphs for \(r\geq 4\)), and for the \(K_r\)-packing problem on cographs.

##### MSC:

05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |

05C85 | Graph algorithms (graph-theoretic aspects) |

05B40 | Combinatorial aspects of packing and covering |

68R10 | Graph theory (including graph drawing) in computer science |