On the chromatic number of q-Kneser graphs

A. Blokhuis, A.E. Brouwer, T.I. Szonyi

Research output: Contribution to journalArticleAcademicpeer-review

12 Citations (Scopus)
1 Downloads (Pure)

Abstract

We show that the q-Kneser graph $qK_{2k:k}$ (the graph on the k-subspaces of a 2k-space over GF(q), where two k-spaces are adjacent when they intersect trivially), has chromatic number $q^k + q^{k-1}$ for k = 3 and for k <q log q - q. We obtain detailed results on maximal cocliques for k = 3. Keywords: Chromatic number – q-analog of Kneser graph
Original languageEnglish
Pages (from-to)187-197
JournalDesigns, Codes and Cryptography
Volume65
Issue number3
DOIs
Publication statusPublished - 2012

Fingerprint Dive into the research topics of 'On the chromatic number of q-Kneser graphs'. Together they form a unique fingerprint.

Cite this