Bipartite coverings and the chromatic number (Q2380224)

Summary: 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: {\parindent=4mm \begin{itemize}\item[{\(\bullet\)}] If the bipartite graphs form a partition of the edges of \(G\), then their number is at least \(2^{\sqrt{\log_2k}}\). This is the first improvement of the easy lower bound of \(\log_2k\), while the Alon-Saks-Seymour conjecture states that this can be improved to \(k-1\). \item[{\(\bullet\)}] The sum of the orders of the bipartite graphs in the cover is at least \((1-o(1))k\log_2k\). This generalizes, in asymptotic form, a result of \textit{G. Katona} and \textit{E. Szemerédi} [Stud. Sci. Math. Hung. 2, 23--28 (1967; Zbl 0147.42804)] who proved that the minimum is \(k\log_2k\) when \(G\) is a clique. \end{itemize}}