2009/03/17 by Mubayi, Dhruv, Vishwanathan, Sundar
#05 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.0903.3048
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: \medskip \noindent \bullet If the bicliques partition the edges of G, then their number is at least 2√(log2 k). This is the first improvement of the easy lower bound of log2 k, while the Alon-Saks-Seymour conjecture states that this can be improved to k-1. \medskip \noindent \bullet The sum of the orders of the bicliques is at least (1-o(1))klog2 k. This generalizes, in asymptotic form, a result of Katona and Szemerédi who proved that the minimum is klog2 k when G is a clique.