2013/07/24 by Trevor Pinto, Pinto, Trevor
Computer Science · Mathematics · #05C70 #05DXX #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #math.CO #msc:05C70 #msc:05DXX
paper · pdf · doi:10.48550/arxiv.1307.6363
12 pages, Journal copy; typos corrected, reference added, Electronic Journal of Combinatorics, Volume 21, Issue 1, 2014
openalex publication_date 2013/07/24 · arxiv created 2014/06/23 · arxiv updated 2014/06/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The biclique cover number (resp. biclique partition number) of a graph G, bc(G) (resp. bp(G)), is the least number of biclique (complete bipartite) subgraphs that are needed to cover (resp. partition) the edges of G. The local biclique cover number (resp. local biclique partition number) of a graph G, lbc(G) (resp. lbp(G)), is the least r such that there is a cover (resp. partition) of the edges of G by bicliques with no vertex in more than r of these bicliques. We show that bp(G) may be bounded in terms of bc(G), in particular, bp(G)≤ (1)/(2)(3bc(G)-1). However, the analogous result does not hold for the local measures. Indeed, in our main result, we show that lbp(G) can be arbitrarily large, even for graphs with lbc(G)=2. For such graphs, G, we try to bound lbp(G) in terms of additional information about biclique covers of G. We both answer and leave open questions related to this. There is a well known link between biclique covers and subcube intersection graphs. We consider the problem of finding the least r(n) for which every graph on n vertices can be represented as a subcube intersection graph in which every subcube has dimension r. We reduce this problem to the much studied question of finding the least d(n) such that every graph on n vertices is the intersection graph of subcubes of a d-dimensional cube.