%0 Journal Article
%T A counterexample to the Alon-Saks-Seymour conjecture and related problems
%A Hao Huang
%A Benny Sudakov
%J Mathematics
%D 2010
%I arXiv
%X 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.
%U http://arxiv.org/abs/1002.4687v1