On the Multichromatic Number of s‐Stable Kneser Graphs

For positive integers n and s , a subset S ⊆ [ n ] is s ‐stable if s ≤ | i − j | ≤ n − s for distinct i , j ∈ S . The s ‐stable r ‐uniform Kneser hypergraphK G r( n , k ) s - s t a b l eis the r ‐uniform hypergraph that has the collection of all s ‐stable k ‐element subsets of [ n ] as vertex set and whose edges are formed by the r ‐tuples of disjoint s ‐stable k ‐element subsets of [ n ]. Meunier ([21][F. Meunier, 2011]) conjectured that for positive integers n , k , r , s with k ≥ 2 , s ≥ r ≥ 2 , and n ≥ s k , the chromatic number of s ‐stable r ‐uniform Kneser hypergraphs is equal to ⌈ n − s ( k − 1 ) r − 1 ⌉ . It is a generalized version of the conjecture proposed by Alon et al. ([1][N. Alon, 2009]). Alon et al. ([1][N. Alon, 2009]) confirmed Meunier's conjecture for r = s = 2 qwith arbitrary positive integer q . Lin et al. ([17][W. Lin, 2010]) studied the k th chromatic number χ k of the Mycielskian of the ordinary Kneser graphs μ ( KG ( n , k ) ) for n ≥ 2 k . They conjectured thatχ k ( μ ( KG ( n , k ) ) ) = χ k ( KGn , k ) + kfor n ≥ 3 k − 1 . The case k = 1 was proved by Mycielski ([22][J. Mycielski, 1955]). Lin et al. ([17][W. Lin, 2010]) confirmed their conjecture for k = 2 , 3 , or when n is a multiple of k or n ≥ 3 k 2 / ln k . In this paper, we investigate the multichromatic number of the usual s ‐stable Kneser graphsK G 2( n , k ) s - s t a b l e. With the help of Fan's (1952) combinatorial lemma, we show that Meunier's conjecture is true for r is a power of 2 and s is a multiple of r , and Lin‐Liu‐Zhu's conjecture is true for n ≥ 3 k .