Multi-Colouring of Kneser Graphs: Notes on Stahl's Conjecture

Abstract

A (finite, undirected) graph is $(n,k)$-colourable if we can assign each vertex a $k$-subset of $\{1,2,\dots ,n\}$ so that adjacent vertices receive disjoint subsets. We consider the following problem: if a graph is $(n,k)$-colourable, then for what pairs $(n^{\prime },k^{\prime })$ is it also $(n^{\prime },k^{\prime })$-colourable? This question can be translated into a question regarding multi-colourings of Kneser graphs, for which Stahl formulated a conjecture in 1976. We present new results, strengthen existing results, and in particular present much simpler proofs of several known cases of the conjecture.

17 pages; presentation in introduction changed