Journalartikel

Jahr der Veröffentlichung: 2023

Seiten: 179-204

Zeitschrift: Journal of Combinatorial Designs

Bandnummer: 31

Heftnummer: 4

ISSN: 1063-8539

eISSN: 1520-6610

Open Access Status: Green

DOI Link: https://doi.org/10.1002/jcd.21875

Verlag: Wiley

Abstract: 
We determine the chromatic number of the Kneser graph q Gamma 7,{3,4} $q{{\rm{\Gamma }}}_{7,\{3,4\}}$ of flags of vectorial type {3,4} $\{3,4\}$ of a rank 7 vector space over the finite field GF(q) $\mathrm{GF}(q)$ for large q $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} $q{{\rm{\Gamma }}}_{2d+1,\{d,d+1\}}$ of flags of vectorial type {d,d+1} $\{d,d+1\}$ of a rank 2d+1 $2d+1$ vector space over GF(q) $\mathrm{GF}(q)$ for large q $q$ as long as the large independent sets of the graphs are only the ones that are known.

Harvard-Zitierstil: D'haeseleer, J., Metsch, K. and Werner, D. (2023) On the chromatic number of some generalized Kneser graphs, Journal of Combinatorial Designs, 31(4), pp. 179-204. https://doi.org/10.1002/jcd.21875

APA-Zitierstil: D'haeseleer, J., Metsch, K., & Werner, D. (2023). On the chromatic number of some generalized Kneser graphs. Journal of Combinatorial Designs. 31(4), 179-204. https://doi.org/10.1002/jcd.21875