  Consider a graph obtained by taking edge disjoint union of $k$ complete
bipartite graphs. Alon, Saks and Seymour conjectured that such graph has
chromatic number at most $k+1$. This well known conjecture remained open for
almost twenty years. In this paper, we construct a counterexample to this
conjecture and discuss several related problems in combinatorial geometry and
communication complexity.
