**Originator(s):** N. Alon, M. Saks, P.D. Seymour

**Conjecture/Question:**
Every union of $m$ pairwise edge-disjoint complete bipartite graphs is
$(m+1)$-colorable.

**Background/motivation:**
This statement is a bipartite analogue of the
Erdos-Faber-Lov\'asz Conjecture.
A special case of it would be the Graham-Pollak Theorem stating that
the minimum number of complete bipartite subgraphs needed to decompose
$K_n$ is $n-1$. Algebraic proofs of this theorem
are known, but no purely combinatorial proofs are known.

**Comments/Partial results:**
The conjecture has been shown to be FALSE. Huang-Sudakov [HS] constructed a
family of counterexamples having a superlinear gap between the chromatic number
and the biclique partition number. They posed a new conjecture that the union
of $m$ edge-disjoint bicliques is $2^{(\log_2 m)^2}$-colorable and that this is
sharp. The new conjecture is related to a conjecture in theoretical computer
science about the complexity of a certain problem.

**References:**

[GP] R.L. Graham and H.O. Pollak, On embedding graphs in squashed cubes. Graph
theory and applications (Proc. Quadrennial Conf. on Graph Theory, Western
Michigan Univ., Kalamazoo, Mich., 1972), Lecture Notes in Math. 303
(Springer, 1972), 99-110.

[HS] H. Huang and B. Sudakov, A counterexample to the Alon-Saks-Seymour
conjecture and related problems,
http://www.math.ucla.edu/~bsudakov/ass-conjecture.pdf ,
Combinatorica, to appear.

Posted 04/06/05; Last update 09/13/11