On the Multichromatic Number of s-Stable Kneser Graphs
For positive integers n and s, a subset [n] is s-stable if for distinct . The s-stable r-uniform Kneser hypergraph is 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]) conjectured that for positive integers with , and , the chromatic number of s-stable r -uniform Kneser hypergraphs is equal to . It is a generalized version of the conjecture proposed by Alon etal. ([1]). Alon etal. ([1]) confirmed Meunier's conjecture for with arbitrary positive integer q. Lin etal. ([17]) studied the kth chromatic number of the Mycielskian of the ordinary Kneser graphs for . They conjectured that for . The case was proved by Mycielski ([22]). Lin etal. ([17]) confirmed their conjecture for , or when n is a multiple of k or .
multichromatic number s-stable kneser graph kneser graph s-stable r-uniform kneser hypergraph mycielskian