On the chromatic number of some generalized Kneser graphs

DOI10.1002/JCD.21875arXiv2205.02632MaRDI QIDQ6187005FDOQ6187005

Authors: Jozefien D'haeseleer, Klaus Metsch, Daniel Werner 

Publication date: 5 February 2024

Published in: Journal of Combinatorial Designs (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

chromatic number\(q\)-analog of generalized Kneser graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Maximal cocliques in the Kneser graph on plane-solid flags in \(\mathrm{PG}(6,q)\)
• Cocliques in the Kneser graph on line-plane flags in \(\mathrm{PG}(4, q)\)
• A Hilton-Milner theorem for vector spaces
• On the chromatic number of \(q\)-Kneser graphs
• Large \(\{0,1,\ldots,t\}\)-cliques in dual polar graphs
• On the chromatic number of two generalized Kneser graphs
• An algebraic approach to Erdős-Ko-Rado sets of flags in spherical buildings

Cited In (1)

• Maximal cocliques and the chromatic number of the Kneser graph on chambers of \(\mathrm{PG}(3, q)\)

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)