A counterexample to the Alon-Saks-Seymour conjecture and related problems

Understand

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.