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\ge 1$ and $0\le 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\ge 2$ in the following further classes of cases: $$\text{Unknown environment 'enumerate'}$$