A new graph decomposition method for bipartite graphs

Abstract

Given a sufficiently large and sufficiently dense bipartite graph $G=(A,B;E),$ we present a novel method for decomposing the majority of the edges of $G$ into quasirandom graphs so that the vertex sets of these quasirandom graphs partition the majority of $A.$ The method works for relatively small or sparse graphs, and can be used to substitute the Regularity lemma of Szemerédi in some graph embedding problems.

Slightly modified version of the extended abstract from the proceedings of MATCOS-19

Cited by in corpus (1)

• Regular decomposition of the edge set of graphs with applications