Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices (Q802577)

The author proves that the edge set of an arbitrary graph G on n vertices can be covered by at most \(n-[\log_ 2n]+1\) complete bipartite subgraphs of G. This result improves the upper bound of J. C. Bermond. If the weight of a subgraph is the number of its vertices, then the author proves that there always exists a cover with total weight \(c(n^ 2/\log n)\) and this bound is best possible apart from a constant factor. This result is a corollary to a more general theorem of the paper which solves a complexity problem of T. G. Tarján.