The chromatic number of almost stable Kneser hypergraphs - École des Ponts ParisTech Accéder directement au contenu
Article Dans Une Revue Journal of Combinatorial Theory, Series A Année : 2011

The chromatic number of almost stable Kneser hypergraphs

Résumé

Let V(n,k,s) be the set of k-subsets S of [n] such that for all i,j∈S, we have |i−j|⩾s. We define almost s-stable Kneser hypergraph View the MathML source to be the r-uniform hypergraph whose vertex set is V(n,k,s) and whose edges are the r-tuples of disjoint elements of V(n,k,s). With the help of a Zp-Tucker lemma, we prove that, for p prime and for any n⩾kp, the chromatic number of almost 2-stable Kneser hypergraphs View the MathML source is equal to the chromatic number of the usual Kneser hypergraphs View the MathML source, namely that it is equal to View the MathML source. Related results are also proved, in particular, a short combinatorial proof of Schrijverʼs theorem (about the chromatic number of stable Kneser graphs) and some evidences are given for a new conjecture concerning the chromatic number of usual s-stable r-uniform Kneser hypergraphs.

Domaines

Autre [cs.OH]

Dates et versions

hal-00676479 , version 1 (05-03-2012)

Identifiants

Citer

Frédéric Meunier. The chromatic number of almost stable Kneser hypergraphs. Journal of Combinatorial Theory, Series A, 2011, 118 (6), pp.1820-1828. ⟨10.1016/j.jcta.2011.02.010⟩. ⟨hal-00676479⟩
80 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More