Bipartite Coverings and the Chromatic Number - Mubayi, Dhruv; Vishwanathan, Sundar (The Electronic Journal of Combinatorics, 2009)
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^_2 k . This is the first improvement of the easy lower bound of _2 k, while the Alon-Saks-Seymour conjecture states that this can be improved to k-1. The sum of the orders of the bipartite graphs in the cover is at least (1-o(1))k_2 k. This generalizes, in asymptotic form, a result of Katona and Szemerédi who proved that the minimum is k_2 k when G is a clique.