A counterexample to the Alon-Saks-Seymour conjecture and related problems
arXiv:1002.4687
Abstract
Consider a graph obtained by taking edge disjoint union of complete bipartite graphs. Alon, Saks and Seymour conjectured that such graph has chromatic number at most . 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.