On the topological lower bound for the multichromatic number

In 1976, Stahl [14] defined the mm-tuple coloring of a graph GG and formulated a conjecture on the multichromatic number of Kneser graphs. For m=1m=1 this conjecture is Kneser’s conjecture, which was proved by Lovász in 1978 [10]. Here we show that Lovász’s topological lower bound given in this way cannot be used to prove Stahl’s conjecture. We obtain that the strongest index bound only gives the trivial m⋅ω(G)m⋅ω(G) lower bound if m≥|V(G)|m≥|V(G)|. On the other hand, the connectivity bound for Kneser graphs is constant if mm is sufficiently large. These findings provide new examples of graphs showing that the gaps between the chromatic number, the index bound and the connectivity bound can be arbitrarily large.