The Kneser graph has as vertices the -element subsets of , with an edge between two exactly when they are disjoint. A graph colouring of this graph partitions the -sets into intersecting families.
For integers , the chromatic number of the Kneser graph is . The upper bound colours by the least element among the first elements, with one final colour for all other sets. The Gale hemisphere lemma and the Lusternik-Schnirelmann-Borsuk theorem give the matching lower bound.
Articles by others on the same topic
A Kneser graph \( K(n, k) \) is a graph defined using the combinatorial structure of sets. Specifically, it is constructed from the set of all \( k \)-element subsets of an \( n \)-element set. The vertices of the Kneser graph correspond to these \( k \)-element subsets, and two vertices (i.e., subsets) are adjacent if and only if the corresponding subsets are disjoint.