Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

The chromatic number of almost stable Kneser hypergraphs

Abstract : 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.
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal-enpc.archives-ouvertes.fr/hal-00676479
Contributeur : Cermics Hal <>
Soumis le : lundi 5 mars 2012 - 14:31:35
Dernière modification le : mercredi 15 avril 2015 - 16:10:27

Lien texte intégral

Identifiants

Collections

Citation

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

Partager

Métriques

Consultations de la notice

159