科研之友
微信
新浪微博
Facebook
分享链接
摘要
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.
- 出版日期2012-3
