On biclique coverings

被引：13

作者：

Bezrukova, Sergei ^{[1
]}

Froncek, Dalibor ^{[2
]}

Rosenberg, Steven J. ^{[1
]}

Kovar, Petr ^{[3
]}

机构：

[1] Univ Wisconsin Superior Belknap & Catlin, Dept Math & Comp Sci, Superior, WI 54880 USA

[2] Univ Minnesota, Dept Math & Stat, Duluth, MN 55812 USA

[3] Tech Univ Ostrava, Dept Math & Descript Geometry, Ostrava 70833, Czech Republic

来源：

DISCRETE MATHEMATICS | 2008年 / 308卷 / 2-3期

关键词：

graph coverings; bicliques; Sperner's theorem; graph composition; lexicographic product;

D O I：

10.1016/j.disc.2006.11.045

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

It was proved by Froncek, Jerebic, Klavzar, and Kovar that if a complete bipartite graph Kn,n with a perfect matching removed can be covered by k bicliques, then n <= ([(k)(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. (c) 2007 Elsevier B.V. All rights reserved.

引用

页码：319 / 323

页数：5