Some Multiple Chromatic Numbers of Kneser Graphs

The Kneser graph \( K(m, n) \) (when \( m > 2n \)) has the \( n \)-subsets of an \( m \)-set as its vertices, two vertices being adjacent in \( K(m, n) \) whenever they are disjoint sets. The \( k \)th-chromatic number of any graph \( G \) (denoted by \( \chi_k(G) \)) is the least integer \( t \) such that the vertices can be assigned \( k \)-subsets of \( \{1, 2, \dots, t\} \) with adjacent vertices receiving disjoint \( k \)-sets. S. Stahl has conjectured that, if \( k = qn – r \) where \( q \geq 1 \) and \( 0 \leq r < n \), then \( \chi_k(K(m, n)) = qm – 2r \). This expression is easily verified when \( r = 0 \); Stahl has also established its validity for \( q = 1 \), for \( m = 2n + 1 \) and for \( k = 2, 3 \). We show here that the expression is also valid for all \( q \geq 2 \) in the following further classes of cases: \begin{enumerate}[label=(\roman*)] \item \( 2n + 1 < m \leq n(2 + r^{-1}) \) (\( 0 < r 1 \));
\item \( 4 \leq n \leq 6 \) and \( 1 \leq r \leq 2 \) (all \( m \));
\item \( 7 \leq n \leq 11 \) and \( r = 1 \) (all \( m \));
\item \( (n, r, m) = (7, 2, 18), (12, 1, 37), (12, 1, 38) \) or \( (13, 1, 40) \).
\end{enumerate}