On the chromatic number of general Kneser hypergraphs

Meysam Alishahi, Hossein Hajiabolhassan

Research output: Contribution to journalJournal articleResearchpeer-review

195 Downloads (Pure)

Abstract

In a break-through paper, Lovász [20] determined the chromatic number of Kneser graphs. This was improved by Schrijver [27], by introducing the Schrijver subgraphs of Kneser graphs and showing that their chromatic number is the same as that of Kneser graphs. Alon, Frankl, and Lovász [2] extended Lovász's result to the usual Kneser hypergraphs and one of our main results is to extend this to a new family of general Kneser hypergraphs. Moreover, as a special case, we settle a question from Naserasr and Tardif [26].In 2011, Meunier introduced almost 2-stable Kneser hypergraphs and determined their chromatic number as an approach to a supposition of Ziegler [35] and a conjecture of Alon, Drewnowski, and Łuczak [3]. In this work, our second main result is to improve this by computing the chromatic number of a large family of Schrijver hypergraphs. Our last main result is to prove the existence of a completely multicolored complete bipartite graph in every coloring of a graph which extends a result of Simonyi and Tardos [29].The first two results are proved using a new improvement of the Dol'nikov-Kříž [7,18] bound on the chromatic number of general Kneser hypergraphs.
Original languageEnglish
JournalJournal of Combinatorial Theory. Series B
Volume115
Issue numberNovember
Pages (from-to)186-209
ISSN0095-8956
DOIs
Publication statusPublished - 2015

Keywords

  • Chromatic number
  • Kneser hypergraphs
  • Zp-Tucker lemma
  • Tucker–Ky Fan’s lemma

Fingerprint Dive into the research topics of 'On the chromatic number of general Kneser hypergraphs'. Together they form a unique fingerprint.

Cite this