Volume 24, Number 1, 163-170, DOI: 10.1007/s00493-004-0011-1

A Combinatorial Proof of Kneser’s Conjecture*

Jiří Matoušek

View Related Documents

Abstract

Kneserrsquos conjecture, first proved by Lovász in 1978, states that the graph with all k-element subsets of {1, 2, . . . , n} as vertices and with edges connecting disjoint sets has chromatic number n–2k+2. We derive this result from Tuckerrsquos combinatorial lemma on labeling the vertices of special triangulations of the octahedral ball. By specializing a proof of Tuckerrsquos lemma, we obtain self-contained purely combinatorial proof of Kneserrsquos conjecture.

Mathematics Subject Classification (2000):  05C15 - 05A05 - 55M35

* Research supported by Charles University grants No. 158/99 and 159/99 and by ETH Zürich.

Fulltext Preview

Image of the first page of the fulltext document