A Parameterized Algorithm for \({K_r}\)-Factors in Graphs of High Minimum Degree

Abstract

Abstract. A [Formula: see text]-factor of a graph [Formula: see text] is a collection of vertex-disjoint [Formula: see text]-cliques covering [Formula: see text]. We prove the following algorithmic version of the classical Hajnal–Szemerédi theorem in graph theory, when [Formula: see text] is considered as a constant. Given [Formula: see text] such that [Formula: see text], let [Formula: see text] be an [Formula: see text]-vertex graph with minimum degree at least [Formula: see text]. Then there is an algorithm with running time [Formula: see text] that outputs either a [Formula: see text]-factor of [Formula: see text] or a certificate showing that none exists, namely, this problem is fixed-parameter tractable in [Formula: see text]. On the other hand, it is known that if [Formula: see text] for fixed [Formula: see text], the problem is NP-C. By taking the complement, our result yields a similar result on the equitable [Formula: see text]-colorings of graphs of maximum degree [Formula: see text], for [Formula: see text]. We indeed establish characterization theorems for this problem, showing that the existence of a [Formula: see text]-factor is equivalent to the existence of certain class of [Formula: see text]-tilings of size [Formula: see text], whose existence can be searched by the color-coding technique developed by Alon, Yuster, and Zwick.