# Complexity of the H-factor problem.

An -factor in a graph is a set of vertex-disjoint copies of covering all vertices of .

**Problem**Let be a fixed positive real number and a fixed graph. Is it NP-hard to determine whether a graph on vertices and minimum degree contains and -factor?

The answer is positive for cliques and a few other graphs [KO06].

If we remove the minimum degree condition, the problem is NP-complete if and only if has a component which contains at least 3 vertices, as shown by Hell and Kirkpatrick [HK].

## Bibliography

[HK] P. Hell and D.G. Kirkpatrick, On the complexity of general graph factor problems, SIAM J. Computing 12 (1983), 601-609.

[KO06] D. Kühn and D. Osthus, Critical chromatic number and the complexity of perfect packings in graphs, Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006.

*[KO09] D. Kühn and D. Osthus, The minimum degree threshold for perfect graph packings, Combinatorica 29 (2009), 65-107.

* indicates original appearance(s) of problem.