Biclique Coverings and the Chromatic Number

Details Biclique Coverings and the Chromatic Number Biclique Coverings and the Chromatic Number

2009-03-17

arxiv.org/abs/0903.3048v1

Mathematics

Combinatorics

Scientific paper

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^{\sqrt{\log_2 k}}$. 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$. \medskip \noindent $\bullet$ The sum of the orders of the bicliques is at least $(1-o(1))k\log_2 k$. This generalizes, in asymptotic form, a result of Katona and Szemer\'edi who proved that the minimum is $k\log_2 k$ when $G$ is a clique.

Affiliated with

Also associated with

No associations

Rating

Biclique Coverings and the Chromatic Number does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Biclique Coverings and the Chromatic Number, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Biclique Coverings and the Chromatic Number will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-400891