On the chromatic number of some generalized Kneser graphs
From MaRDI portal
Publication:6187005
Abstract: We determine the chromatic number of the Kneser graph q{Gamma}_{7,{3,4}} of flags of vectorial type {3, 4} of a rank 7 vector space over the finite field GF(q) for large q and describe the colorings that attain the bound. This result relies heavily, not only on the independence number, but also on the structure of all large independent sets. Furthermore, our proof is more general in the following sense: it provides the chromatic number of the Kneser graphs q{Gamma}_{2d+1,{d,d+1}} of flags of vectorial type {d, d+1} of a rank 2d+1 vector space over GF(q) for large q as long as the large independent sets of the graphs are only the ones that are known.
Recommendations
- On the chromatic number of two generalized Kneser graphs
- On the chromatic number of \(q\)-Kneser graphs
- The chromatic number of two families of generalized Kneser graphs related to finite generalized quadrangles and finite projective 3-spaces
- Maximal cocliques and the chromatic number of the Kneser graph on chambers of \(\mathrm{PG}(3, q)\)
- The chromatic number of the q-Kneser graph for large q
Cites work
- scientific article; zbMATH DE number 1101474 (Why is no real title available?)
- A Hilton-Milner theorem for vector spaces
- An algebraic approach to Erdős-Ko-Rado sets of flags in spherical buildings
- Cocliques in the Kneser graph on line-plane flags in \(\mathrm{PG}(4, q)\)
- Large \(\{0,1,\ldots,t\}\)-cliques in dual polar graphs
- Maximal cocliques in the Kneser graph on plane-solid flags in \(\mathrm{PG}(6,q)\)
- On the chromatic number of \(q\)-Kneser graphs
- On the chromatic number of two generalized Kneser graphs
Cited in
(1)
This page was built for publication: On the chromatic number of some generalized Kneser graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6187005)
