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

DOI10.37236/10239zbMATH Open1467.51006arXiv2102.06688OpenAlexW3182358330MaRDI QIDQ2039997FDOQ2039997

Authors: Klaus Metsch 

Publication date: 6 July 2021

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

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.

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

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

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\)

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)

Cites Work

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

Cited In (10)

• Colouring quadrangulations of projective spaces
• On the chromatic number of \(q\)-Kneser graphs
• 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)