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.
http://i.stanford.edu/pub/cstr/reports/cs/tr/75/489/CS-TR-75-489.pdf