Homepage
Curriculum vitae
Publications
Teaching (czech)
Contact
   

On biclique coverings

A simpler proof and more general results on biclique coverings of graphs.

Abstract

It was proved in "Strong isometric dimension, biclique coverings, and Sperner's Theorem" that if a complete bipartite graph Kn,n with a perfect matching removed can be covered by k bicliques, then n ≤ (k choose ⌊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.

Status

Submitted for publication to special volume of Discrete Mathematics (DM).
S. Bezrukov, D. Fronček, P. Kovář, S. J. Rosenberg, On biclique coverings, Discrete Math. 308, p. 319-323 (2008)


email
phone ++420 / 597 325 972
Last update: 29.12.2011