Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR10-026 | 25th February 2010 05:09

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

RSS-Feed




TR10-026
Authors: Hao Huang, Benny Sudakov
Publication: 25th February 2010 13:50
Downloads: 3806
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint