Some Multiple Chromatic Numbers of Kneser Graphs

Abstract

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:

1. \( 2n + 1 < m \leq n(2 + r^{-1}) \) (\( 0 < r 1 \));
2. \( 4 \leq n \leq 6 \) and \( 1 \leq r \leq 2 \) (all \( m \));
3. \( 7 \leq n \leq 11 \) and \( r = 1 \) (all \( m \));
4. \( (n, r, m) = (7, 2, 18), (12, 1, 37), (12, 1, 38) \) or \( (13, 1, 40) \).