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 quadranglesgeneralized Kneser graphsfinite projective 3-spaces

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Combinatorial aspects of finite geometries (05B25) 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.

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

(10)

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

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)