Sparse Balanced Partitions and the Complexity of Subgraph Problems
Noga Alon, Dániel Marx · SIAM Journal on Discrete Mathematics · 2011
We consider the problem of partitioning the vertices of an [Formula: see text]-vertex graph with maximum degree [Formula: see text] into [Formula: see text] classes [Formula: see text] of size at most [Formula: see text] in a way that minimizes the number of pairs [Formula: see text] for which there is an edge between [Formula: see text] and [Formula: see text]. We show that there is always such a partition with [Formula: see text] adjacent pairs, and this bound is tight. This problem is related to questions about the depth of certain graph embeddings, which have been used in the study of the complexity of subgraph and constraint satisfaction problems. (A corrected version of this paper has been appended to the originally posted pdf.)