Recognition: unknown
A counterexample to the Alon-Saks-Seymour conjecture and related problems
classification
🧮 math.CO
keywords
conjecturecounterexamplegraphproblemsrelatedalmostalonalon-saks-seymour
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.