On biclique coverings

Sergei Bezrukov, Dalibor Fronček, Steven J. Rosenberg, Petr Kovář

Research output: Contribution to journalArticlepeer-review

13 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)319-323
Number of pages5
JournalDiscrete Mathematics
Volume308
Issue number2-3
DOIs
StatePublished - Feb 6 2008

Keywords

  • Bicliques
  • Graph composition
  • Graph coverings
  • Lexicographic product
  • Sperner's Theorem

Fingerprint Dive into the research topics of 'On biclique coverings'. Together they form a unique fingerprint.

Cite this