# zbMATH — the first resource for mathematics

The $$K_r$$-packing problem. (English) Zbl 0978.05060
Summary: 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.

##### 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
Full Text: