Key points are not available for this paper at this time.
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.
Heuvel et al. (Mon,) studied this question.