Regular Partitions of Graphs,
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1975
- Accession Number
- ADA011833
Entities
People
- E. Szemeredi
Organizations
- Stanford University