Almost Regular Decompositions of a Graph

Abstract

Let k ≤ 8 be a positive integer, and let G be a graph on n vertices such that the degree of each its vertex is at least\( \frac{k-1}{k} \). It is proved that the vertex set of G can be partitioned into several cliques of size at most k so that for each positive integer k₀< k, there is at most one clique of size k₀in this partition. Bibliography: 2 titles.