1975•Defense Technical Information Center (DTIC)Requires access
REGULAR PARTITIONS OF GRAPHS
Endre Szemerédi
Open publisher page 803 citations
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 the author generalizes this result to arbitrary graphs, at the same time strengthening and simplifying the original bipartite result.