On the chromatic number of q-Kneser graphs

Research output: Contribution to journalArticleAcademicpeer-review

  • 6 Citations

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
LanguageEnglish
Pages187-197
JournalDesigns, Codes and Cryptography
Volume65
Issue number3
DOIs
StatePublished - 2012

Fingerprint

Kneser Graph
Chromatic number
K-space
Q-analogue
Intersect
Adjacent
Subspace
Graph in graph theory

Cite this

@article{a088ae8d3bc64a45a7a05fb8aa655afc,
title = "On the chromatic number of q-Kneser graphs",
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",
author = "A. Blokhuis and A.E. Brouwer and T.I. Szonyi",
year = "2012",
doi = "10.1007/s10623-011-9513-1",
language = "English",
volume = "65",
pages = "187--197",
journal = "Designs, Codes and Cryptography",
issn = "0925-1022",
publisher = "Springer",
number = "3",

}

On the chromatic number of q-Kneser graphs. / Blokhuis, A.; Brouwer, A.E.; Szonyi, T.I.

In: Designs, Codes and Cryptography, Vol. 65, No. 3, 2012, p. 187-197.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - On the chromatic number of q-Kneser graphs

AU - Blokhuis,A.

AU - Brouwer,A.E.

AU - Szonyi,T.I.

PY - 2012

Y1 - 2012

N2 - 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

AB - 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

U2 - 10.1007/s10623-011-9513-1

DO - 10.1007/s10623-011-9513-1

M3 - Article

VL - 65

SP - 187

EP - 197

JO - Designs, Codes and Cryptography

T2 - Designs, Codes and Cryptography

JF - Designs, Codes and Cryptography

SN - 0925-1022

IS - 3

ER -