The chromatic number of a two families of generalized Kneser graphs related to finite generalized quadrangles and finite projective 3-spaces

preprint2021arXivOpen access

Abstract

Let ΓΓ be the graph whose vertices are the chambers of the finite projective space PG(3,q)PG(3,q) with two vertices being adjacent when the corresponding chambers are in general position. It is known that the independence number of this graph is (q2+q+1)(q+1)2(q^2+q+1)(q+1)^2. For q≥43q\ge 43 we determine the largest independent set of ΓΓ and show that every maximal independent set that is not a largest one has at most constant times q3q^3 elements. For q≥47q\ge 47, this information is then used to show that ΓΓ has chromatic number q2+qq^2+q. Furthermore, for many families of generalized quadrangles we prove similar results for the graph that is built in the same way on the chambers of the generalized quadrangle.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.