Speaker: Valerie Watts, Carleton
University
Time and Place: 5 November 2004, 1:00 pm, HP 4351, Carleton University
Title: Fractional biclique covers and partitions of graphs
Abstract:
A biclique is a complete bipartite subgraph of a graph G. The
biclique cover number, bc(G), and the biclique partition number,
bp(G), are the minimum number of bicliques needed to cover and
partition, respectively, the edges of G. Since bc(G) and bp(G) are
integer-valued graph parameters, they may be viewed as integer
programs. This talk will look at the linear relaxation of these
integer programs and present linear programs which define the
fractional biclique cover number, bc*(G), and the fractional
biclique partition number, bp*(G). Also, this talk will observe
that bc*(G) and bp*(G) provide lower bounds on bc(G) and bp(G)
respectively and conditions for equality will be given.
Corresponding fractional analogues for results about bc(G) and
bp(G) will be presented.