ACTA issues

A lower bound on the multichromatic number of Kneser graphs

József Osztényi

Acta Sci. Math. (Szeged) 74:1-2(2008), 289-296

Abstract. In 1976, S. Stahl formulated the conjecture on the multichromatic number of the Kneser graphs: For any positive integers $m$ and $n$ with $m\geq2n$, $\chi_{nq+r}(KG_{m,n})=mq+m-2n+2r$, where $0\leq q$ and $0< r \leq n$. It is well kown that $\chi_{nq}(KG_{m,n})=mq$, moreover, Stahl's conjecture is equivalent to the claim that $\chi_{nq+1}(KG_{m,n})\geq mq+m-2n+2$. In $[4]$ Stahl proved that the gap between $\chi_{nq}$ and $\chi_{nq+1}$ is arbitrarily large if $n$ is fixed and $m$ is large enough. We shall prove here that $\chi_{nq+1}(KG_{m,n})\geq mq+3$ for any positive integers $m,n$ and $q$.

AMS Subject Classification (1991): 05C15

Received January 9, 2007, and in revised form April 11, 2007. (Registered under 1/2007.)