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 ... more >>>