Journalartikel

Jahr der Veröffentlichung: 2024

Seiten: 388-409

Zeitschrift: Journal of Combinatorial Designs

Bandnummer: 32

Heftnummer: 7

ISSN: 1063-8539

eISSN: 1520-6610

Open Access Status: Hybrid

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

Verlag: Wiley

Abstract: 
Let Gamma be the graph whose vertices are the chambers of the finite projective 3-space PG(3,q), with two vertices being adjacent if and only if the corresponding chambers are in general position. We show that a maximal independent set of vertices of Gamma contains q(4)+3q(3)+4q(2)+3q+1, or 3q(3)+5q(2)+3q+1, or at most 3q(3)+4q(2)+3q+2 elements. For q >= 4 the structure of the largest maximal independent sets is described. For q >= 7 the structure of the maximal independent sets of the three largest cardinalities is described. Using the cardinality of the second largest maximal independent sets, we show that the chromatic number of Gamma is q(2)+q.

Harvard-Zitierstil: Heering, P. and Metsch, K. (2024) Maximal cocliques and the chromatic number of the Kneser graph on chambers of PG(3,q) (3,q), Journal of Combinatorial Designs, 32(7), pp. 388-409. https://doi.org/10.1002/jcd.21940

APA-Zitierstil: Heering, P., & Metsch, K. (2024). Maximal cocliques and the chromatic number of the Kneser graph on chambers of PG(3,q) (3,q). Journal of Combinatorial Designs. 32(7), 388-409. https://doi.org/10.1002/jcd.21940