TY - JOUR

T1 - On biclique coverings

AU - Bezrukov, Sergei

AU - Fronček, Dalibor

AU - Rosenberg, Steven J.

AU - Kovář, Petr

PY - 2008/2/6

Y1 - 2008/2/6

N2 - It was proved by Fronček, Jerebic, Klavžar, and Kovář that if a complete bipartite graph Kn, n with a perfect matching removed can be covered by k bicliques, then n ≤ fenced(frac(k, ⌊ frac(k, 2) ⌋)). 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.

AB - It was proved by Fronček, Jerebic, Klavžar, and Kovář that if a complete bipartite graph Kn, n with a perfect matching removed can be covered by k bicliques, then n ≤ fenced(frac(k, ⌊ frac(k, 2) ⌋)). 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.

KW - Bicliques

KW - Graph composition

KW - Graph coverings

KW - Lexicographic product

KW - Sperner's Theorem

UR - http://www.scopus.com/inward/record.url?scp=36248977676&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=36248977676&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2006.11.045

DO - 10.1016/j.disc.2006.11.045

M3 - Article

AN - SCOPUS:36248977676

VL - 308

SP - 319

EP - 323

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 2-3

ER -