Record Details

Bipartite Coverings and the Chromatic Number

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Bipartite Coverings and the Chromatic Number
 
Creator MUBAYI, D
VISHWANATHAN, S
 
Description Consider a graph G with chromatic number k and a collection of complete bipartite graphs, or bicliques, that cover the edges of G. We prove the following two results: If the bipartite graphs form a partition of the edges of G, then their number is at least 2 root(log2k). This is the first improvement of the easy lower bound of log(2)k, while the Alon-Saks-Seymour conjecture states that this can be improved to k - 1. The sum of the order soft he bipartite graphs in the cover is atleast (1 - o(1))k log(2)k. This generalizes, in asymptotic form, a result of Katona and Szemeredi who proved that the minimum is k log(2)k when G is a clique.
 
Publisher ELECTRONIC JOURNAL OF COMBINATORICS
 
Date 2011-07-21T15:12:00Z
2011-12-26T12:52:03Z
2011-12-27T05:39:00Z
2011-07-21T15:12:00Z
2011-12-26T12:52:03Z
2011-12-27T05:39:00Z
2009
 
Type Article
 
Identifier ELECTRONIC JOURNAL OF COMBINATORICS, 16(1), -
1077-8926
http://dspace.library.iitb.ac.in/xmlui/handle/10054/5904
http://hdl.handle.net/10054/5904
 
Language en