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

DOI10.37236/10239MaRDI QIDQ2039997zbMATH OpenOpenAlexFDO

Authors Klaus Metsch

Publication date 6 July 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2102.06688

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

chromatic numberfinite generalized quadranglesfinite projective 3-spacesgeneralized Kneser graphs

Mathematics Subject Classification ID

Combinatorial aspects of finite geometries (05B25) Planar graphs; geometric and topological aspects of graph theory (05C10) Generalized quadrangles and generalized polygons in finite geometry (51E12) Combinatorial structures in finite projective spaces (51E20)

Abstract: Let $Gamma$ be the graph whose vertices are the chambers of the finite projective space $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 $(q^2+q+1)(q+1{)}^2$. For $qge43$ we determine the largest independent set of $Gamma$ and show that every maximal independent set that is not a largest one has at most constant times $q^3$ elements. For $qge47$, this information is then used to show that $Gamma$ has chromatic number $q^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.

Review text

Summary: Let \(\Gamma\) be the graph whose vertices are the chambers of the finite projective space \(\text{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 \((q^2+q+1)(q+1)^2\). For \(q\geqslant 43\) we determine the largest independent set of \(\Gamma\) and show that every maximal independent set that is not a largest one has at most constant times \(q^3\) elements. For \(q\geqslant 47\), this information is then used to show that \(\Gamma\) has chromatic number \(q^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.

Recommendations

• On the chromatic number of \(q\)-Kneser graphs
• On the chromatic number of two generalized Kneser graphs
• Colouring lines in projective space
• Colouring quadrangulations of projective spaces
• The chromatic number of the q-Kneser graph for large q

Cites work

• A Hilton-Milner theorem for vector spaces
• Cocliques in the Kneser graph on line-plane flags in \(\mathrm{PG}(4, q)\)
• Colouring lines in projective space
• Finite generalized quadrangles
• How many \(s\)-subspaces must miss a point set in \(\mathrm{PG}(d, q)\)
• On the chromatic number of \(q\)-Kneser graphs
• The Erdős-Ko-Rado theorem for vector spaces

Cited in

(11)

• The chromatic number of the q-Kneser graph for large q
• Maximal cocliques in the Kneser graph on plane-solid flags in \(\mathrm{PG}(6,q)\)
• On the chromatic number of two generalized Kneser graphs
• Colouring quadrangulations of projective spaces
• The chromatic index of finite projective spaces
• On the chromatic number of some generalized Kneser graphs
• Maximal cocliques and the chromatic number of the Kneser graph on chambers of \(\mathrm{PG}(3, q)\)
• On the chromatic number of \(q\)-Kneser graphs
• On the largest independent sets in the Kneser graph on chambers of \(\mathrm{PG}(4, \mathrm{q})\)
• Cocliques in the Kneser graph on line-plane flags in \(\mathrm{PG}(4, q)\)
• Colouring lines in projective space

This page was built for publication: The chromatic number of two families of generalized Kneser graphs related to finite generalized quadrangles and finite projective 3-spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2039997)