Accession Number:

ADA011833

Title:

Regular Partitions of Graphs,

Descriptive Note:

Corporate Author:

STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1975-04-01

Pagination or Media Count:

11.0

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.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE