Colouring lines in projective space

DOI10.1016/J.JCTA.2005.01.010MaRDI QIDQ817609zbMATH OpenOpenAlexFDO

Authors Ameera Chowdhury, Chris Godsil, Gordon Royle

Publication date 16 March 2006

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0507319, https://resolver.caltech.edu/CaltechAUTHORS:20170408-204250029

zbMATH Keywords

chromatic numberKneser graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: Let $V$ be a vector space of dimension $v$ over a field of order $q$. The $q$-Kneser graph has the $k$-dimensional subspaces of $V$ as its vertices, where two subspaces $alpha$ and $$ are adjacent if and only if $$ is the zero subspace. This paper is motivated by the problem of determining the chromatic numbers of these graphs. This problem is trivial when $k=1$ (and the graphs are complete) or when $v<2k$ (and the graphs are empty). We establish some basic theory in the general case. Then specializing to the case $k=2$, we show that the chromatic number is $q^2+q$ when $v=4$ and $(q^{v-1}-1)/(q-1)$ when $v>4$. In both cases we characterise the minimal colourings.

Recommendations

• On the chromatic number of \(q\)-Kneser graphs
• A Hilton-Milner theorem for vector spaces
• The chromatic number of two families of generalized Kneser graphs related to finite generalized quadrangles and finite projective 3-spaces
• On the chromatic number of two generalized Kneser graphs
• Colouring quadrangulations of projective spaces

Cites work

• A characterization of flat spaces in a finite geometry and the uniqueness of the hamming and the MacDonald codes
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 428989 (Why is no real title available?)
• Independent sets in association schemes
• Kneser's conjecture, chromatic number, and homotopy
• n-tuple colorings and associated graphs
• The Erdős-Ko-Rado theorem for vector spaces
• The exact bound in the Erdős-Ko-Rado theorem

Cited in

(16)

• Linear spaces with small generated subspaces
• Monochromatic affine lines in finite vector spaces
• The chromatic number of the q-Kneser graph for large q
• Erdős-Ko-Rado theorem, Grassmann graphs and \(p^s\)-Kneser graphs for vector spaces over a residue class ring
• The chromatic number of two families of generalized Kneser graphs related to finite generalized quadrangles and finite projective 3-spaces
• On the \(P_3\)-hull numbers of \(q\)-Kneser graphs and Grassmann graphs
• Colouring quadrangulations of projective spaces
• The maximum size of a partial spread in a finite projective space
• Graph homomorphisms via vector colorings
• Theorems of Erdős-Ko-Rado type in geometrical settings
• The energy of \(q\)-Kneser graphs and attenuated \(q\)-Kneser graphs
• Color Visualization of Blaschke Self-Mappings of the Real Projective Plan
• On q-analogues and stability theorems
• On the chromatic number of \(q\)-Kneser graphs
• On the chromatic number of Grassmann graphs
• On finite simple groups and Kneser graphs.

This page was built for publication: Colouring lines in projective space

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