| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4650881 | Discrete Mathematics | 2008 | 5 Pages |
Abstract
It was proved by Fronček, Jerebic, Klavžar, and Kovář that if a complete bipartite graph Kn,nKn,n with a perfect matching removed can be covered by k bicliques, then n⩽k⌊k2⌋. We give a slightly simplified proof and we show that the result is tight. Moreover, we use the result to prove analogous bounds for coverings of some other classes of graphs by bicliques.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Sergei Bezrukov, Dalibor Fronček, Steven J. Rosenberg, Petr Kovář,