On the chromatic number of q-Kneser graphs

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

doi:10.1007/s10623-011-9513-1

On the chromatic number of q-Kneser graphs

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

Discrete Algebra and Geometry

Research output: Contribution to journal › Article › Academic › peer-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 language	English
Pages (from-to)	187-197
Journal	Designs, Codes and Cryptography
Volume	65
Issue number	3
DOIs	https://doi.org/10.1007/s10623-011-9513-1
Publication status	Published - 2012

Access to Document

10.1007/s10623-011-9513-1

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

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",

}

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

JF - Designs, Codes and Cryptography

SN - 0925-1022

IS - 3

ER -