Considers partitions of the vertices of a graph into equal subsets, with few pairs of subsets connected by edges. (Equivalently we view the graph as a subgraph of a product in which one factor is sparse.) A random graph construction shows that such a factorization does not always exist.
(BibTeX -- Full paper -- CiteSeer -- ACM DL)
Co-authors -- Publications -- David Eppstein -- Theory Group -- Inf. & Comp. Sci. -- UC Irvine
Semi-automatically filtered from a common source file.