The chromatic number of two families of generalized Kneser graphs related to finite generalized quadrangles and finite projective 3-spaces

被引:2
作者
Metsch, Klaus [1 ]
机构
[1] Justus Liebig Univ, Math Inst, Arndtstr 2, D-35392 Giessen, Germany
关键词
D O I
10.37236/10239
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Let Gamma be the graph whose vertices are the chambers of the finite projective space PG(3, q) with two vertices being adjacent when the corresponding chambers are in general position. It is known that the independence number of this graph is (q(2) + q + 1)(q + 1)(2). For q >= 43 we determine the largest independent set of F and show that every maximal independent set that is not a largest one has at most constant times q(3) elements. For q >= 47, this information is then used to show that F has chromatic number q(2) + q. Furthermore, for many families of generalized quadrangles we prove similar results for the graph that is built in the same way on the chambers of the generalized quadrangle.
引用
收藏
页数:12
相关论文
共 10 条
  • [1] On the chromatic number of q-Kneser graphs
    Blokhuis, A.
    Brouwer, A. E.
    Szonyi, T.
    [J]. DESIGNS CODES AND CRYPTOGRAPHY, 2012, 65 (03) : 187 - 197
  • [2] Blokhuis A, 2010, ELECTRON J COMB, V17
  • [3] Cocliques in the Kneser graph on line-plane flags in PG(4;q)
    Blokhuis, Aart
    Brouwer, Andries E.
    [J]. COMBINATORICA, 2017, 37 (05) : 795 - 804
  • [4] BROUWER AE, COMMUNICATION
  • [5] Colouring lines in projective space
    Chowdhury, A
    Godsil, C
    Royle, G
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES A, 2006, 113 (01) : 39 - 52
  • [6] De Beule J, ARXIV200701104, P2020
  • [7] Dhaeseleer J., 2020, ARXIV200505762
  • [8] THE ERDOS-KO-RADO THEOREM FOR VECTOR-SPACES
    FRANKL, P
    WILSON, RM
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES A, 1986, 43 (02) : 228 - 236
  • [9] How many s-subspaces must miss a point set in PG(d, q)
    Metsch, Klaus
    [J]. JOURNAL OF GEOMETRY, 2007, 86 (1-2) : 154 - 164
  • [10] Payne SE, 2009, EMS SER LECT MATH, P1