Report Number: CS-TR-75-489
Institution: Stanford University, Department of Computer Science
Title: Regular partitions of graphs.
Author: Szemeredi, Endre
Date: April 1975
Abstract: A crucial lemma in recent work of the author (showing that
k-term arithmetic progression-free sets of integers must have
density zero) stated (approximately) that any large bipartite
graph can be decomposed into relatively few "nearly regular"
bipartite subgraphs. In this note we generalize this result
to arbitrary graphs, at the same time strengthening and
simplifying the original bipartite result.