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

If a graph is n-colourable, then it obviously is $n'$-colourable for any n'≥ n. But the situation is not so clear when we consider multi-colourings of graphs. A graph is $(n,k)$-colourable if we can assign each vertex a k-subset of \1,2,…,n\ so that adjacent vertices receive disjoint subsets. In this note we consider the following problem: if a graph is $(n,k)$-colourable, then for what pairs $(n', k')$ is it also $(n',k')$-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.