On covering graphs by complete bipartite subgraphs |
| |
Authors: | S. Jukna |
| |
Affiliation: | a Institute of Mathematics, Akademijos 4, LT-80663 Vilnius, Lithuania b Steklov Institute of Mathematics, Fontanka 27, RU-191023 St. Petersburg, Russia |
| |
Abstract: | We prove that, if a graph with e edges contains m vertex-disjoint edges, then m2/e complete bipartite subgraphs are necessary to cover all its edges. Similar lower bounds are also proved for fractional covers. For sparse graphs, this improves the well-known fooling set lower bound in communication complexity. We also formulate several open problems about covering problems for graphs whose solution would have important consequences in the complexity theory of boolean functions. |
| |
Keywords: | Edge clique covering number Biclique Fractional covers Boolean functions Communication complexity |
本文献已被 ScienceDirect 等数据库收录! |
|