Covering multigraphs with bipartite graphs

Abstract: Hansel's lemma states that

s u m_{H i n m a t h c a l H} | H | g e q n l o g_{2} n

holds where

m a t h c a l H

is a collection of bipartite graphs covering all the edges of

K_{n}

. We generalize this lemma to the corresponding multigraph covering problem and the graphon covering problem. We also prove an upper bound on

s u m_{H i n m a t h c a l H} | H |

which shows that our generalization is asymptotically tight in some sense.

This page was built for publication: Covering multigraphs with bipartite graphs