On the chromatic number of \(q\)-Kneser graphs
type: Item
instance of: scholarly article
title: On the chromatic number of \(q\)-Kneser graphs
zbMATH Open document ID: 1266.51008
published in: Designs, Codes and Cryptography
publication date: 2012-11-28T00:00:00Z
review text: This is a very interesting paper that contains strong results that are outcome of difficult computations. The \(q\)-analog \(qK_{n:k}\) of the Kneser graph has the \(k\)-dimensional subspaces of an \(n\)-dimensional vector space over \(\mathrm{GF}(q)\) as vertices with two vertices adjacent if the corresponding subspaces have trivial intersection. This paper studies the chromatic number of \(qK_{2k:k}\) and shows that the chromatic number equals \(q^k + q^{k - 1}\) when \(k = 3\) and also when \(k < q{\log q} - q\). The technique of proof is based on the largest coclique in a \(q\)-Kneser graph which is the dual of the Erdős-Ko-Rado system, and in the situation under consideration, this amounts to taking all the \(k\)-dimensional subspaces of a hyperplane (i.e. a \((2k - 1)\)-dimensional subspace). The second largest conjectured coclique is given by Hilton and Milner and is considerably more technical in its description. These two largest cocliques are used in proving the results in this paper. The paper also makes a detailed and interesting analysis of the case \(qK_{6:3}\).
Mathematics Subject Classification ID: 51E20
Mathematics Subject Classification ID: 05B25
Mathematics Subject Classification ID: 05D99
zbMATH DE Number: 6110827
zbMATH Keywords: chromatic number of a graph
zbMATH Keywords: Kneser graph
zbMATH Keywords: \(q\)-analog
author: Aart Blokhuis
author: Andries E. Brouwer
author: Tamás Szőnyi
reviewed by: Sharad Sane
MaRDI profile type: Publication
full work available at URL: s10623-011-9513-1
OpenAlex ID: W2171798635
cites work: A Hilton-Milner theorem for vector spaces
cites work: Minimal covers of the Klein quadric
cites work: The Erdős-Ko-Rado theorem for vector spaces
cites work: Independent sets in association schemes
cites work: Intersection theorems for systems of finite vector spaces
DOI: 10.1007/S10623-011-9513-1
description: scientific article; zbMATH DE number 6110827