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

Hao Huang, Benny Sudakov

Research output: Contribution to journalArticlepeer-review

13 Scopus citations

Abstract

Consider a graph obtained by taking an edge disjoint union of k complete bipartite graphs. Alon, Saks, and Seymour conjectured that such graphs have 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.

Original languageEnglish (US)
Pages (from-to)205-219
Number of pages15
JournalCombinatorica
Volume32
Issue number2
DOIs
StatePublished - Mar 1 2012

Fingerprint Dive into the research topics of 'A counterexample to the Alon-Saks-Seymour conjecture and related problems'. Together they form a unique fingerprint.

Cite this