Colouring lines in projective space

DOI10.1016/J.JCTA.2005.01.010zbMATH Open1082.05035arXivmath/0507319OpenAlexW2140390981MaRDI QIDQ817609FDOQ817609

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)

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.

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

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

zbMATH Keywords

chromatic numberKneser graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A characterization of flat spaces in a finite geometry and the uniqueness of the hamming and the MacDonald codes
• Kneser's conjecture, chromatic number, and homotopy
• The exact bound in the Erdős-Ko-Rado theorem
• n-tuple colorings and associated graphs
• The Erdős-Ko-Rado theorem for vector spaces
• Independent sets in association schemes

Cited In (15)

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

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)