On bipartite coverings of graphs and multigraphs

Abstract

A bipartite covering of a (multi)graph $G$ is a collection of bipartite graphs, so that each edge of $G$ belongs to at least one of them. The capacity of the covering is the sum of the numbers of vertices of these bipartite graphs. In this note we establish a (modest) strengthening of old results of Hansel and of Katona and Szemerédi, by showing that the capacity of any bipartite covering of a graph on $n$ vertices in which the maximum size of an independent set containing vertex number $i$ is ${\alpha }_i$, is at least ${\sum }_i{\log }_2(n/{\alpha }_i).$ We also obtain slightly improved bounds for a recent result of Kim and Lee about the minimum possible capacity of a bipartite covering of complete multigraphs.