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

Jan van den Heuvel, Xinyi Xu

Published 2024-07-08Version 1

If a graph is $n$-colourable, then it obviously is $n'$-colourable for any $n'\ge 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,\ldots,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.