Proof of Stahl's conjecture in some new cases (Q2197410)

Given positive integers \(s\) and \(t\), an \(s\)-tuple coloring of a graph \(G\) with \(t\) colors is an assignment of \(s\) distinct colors to each vertex of \(G\) such that no two adjacent vertices share a color. The smallest integer \(t\) for which \(G\) has an \(s\)-tuple coloring with \(t\) colors is called the \(s\)th-multichromatic number of \(G\) and denoted by \(\chi_{s}(G)\). For positive integers \(m\), \(n\) with \(m \geq 2n\), the Kneser graph \(KG_{m,n}\) has as vertices all \(n\)-subsets of \(\{1, \ldots, m\}\), two vertices being connected by an edge if the corresponding subsets are disjoint. \textit{S. Stahl} [J. Comb. Theory, Ser. B 20, 185--203 (1976; Zbl 0293.05115)] formulated the conjecture that for all \(2n \le m\) and \(q\), \(0 \le r < n\), \(\chi_{nq-r}(KG_{m,n})=mq-2r\). \textit{L. Lovász} [J. Comb. Theory, Ser. A 25, 319--324 (1978; Zbl 0418.05028)] has proved the conjecture for \(nq-r=1\). Stahl [loc. cit.] showed it for \(r=0\) and also that \(\chi_{s+1} \geq \chi_{s}+2\) for any positive integer \(s\), which proved the conjecture for \(1 < s \le n\). \textit{S. Stahl} [loc. cit.; Discrete Math. 185, No. 1--3, 287--291 (1998; Zbl 0956.05045)] also settled the cases \(n=2,3\) and \(m=2n+1\), and \textit{J. Kincses} et al. [Eur. J. Comb. 34, No. 2, 502--511 (2013; Zbl 1254.05116)] the case \(m=10\) and \(n=4\). Finally, the conjecture is known to hold for \(s=qn\). In this paper, a new lower bound on the multichromatic number of Kneser graphs \(KG_{m,n}\) is presented and shown to be sharp for graph parameters \(2n < m < 3n\) and cases \(qn - \frac{n}{m-2n} < s < qn\) hereby confirming Stahl's conjecture [loc. cit.] for these new cases.