Maximal cocliques and the chromatic number of the Kneser graph on chambers of \(\mathrm{PG}(3, q)\). (English) Zbl 1543.05053
Summary: Let \(\Gamma\) be the graph whose vertices are the chambers of the finite projective 3-space \(\mathrm{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 \geq 4\) the structure of the largest maximal independent sets is described. For \(q \geq 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\).
© 2024 The Authors. Journal of Combinatorial Designs published by Wiley Periodicals LLC.
© 2024 The Authors. Journal of Combinatorial Designs published by Wiley Periodicals LLC.
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05C35 | Extremal problems in graph theory |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 51E20 | Combinatorial structures in finite projective spaces |
| 05D05 | Extremal set theory |
Keywords:
\(q\)-analog of generalized Kneser graph; chromatic number; Erdős-Ko-Rado problem; maximal independent setReferences:
| [1] | J.Bamberg, A.Betten, P.Cara, J.De Beule, M.Lavrauw, M.Neunhoeffer, and M.Horn, FinInG, finite incidence geometry, Version 1.5.6. Refereed GAP package. https://gap-packages.github.io/FinInG, July 2023. |
| [2] | A.Blokhuis, A. E.Brouwer, and T.Szőnyi, Maximal cocliques in the Kneser graph on point‐plane flags in \(PG(4,q)\), Eur. J. Combin. 35 (2014), 95-104. · Zbl 1292.05204 |
| [3] | A.Blokhuis and A. E.Brouwer, Cocliques in the Kneser graph on line‐plane flags in \(PG(4,q)\), Combinatorica. 37 (2017), no. 5, 795-804. · Zbl 1399.05120 |
| [4] | A.Blokhuis, A. E.Brouwer and Ç.Gü ven, Cocliques in the Kneser graph on the point‐hyperplane flags of a projective space, Combinatorica. 34 (2014), no. 1, 1-10. · Zbl 1340.05202 |
| [5] | J.De Beule, S.Mattheus, and K.Metsch, An algebraic approach to Erdös‐Ko‐Rado sets of flags in spherical buildings, J. Combin. Theory Ser. A. 192 (2022), Paper No. 105657, 33. · Zbl 1496.05182 |
| [6] | The GAP Group, GAP—Groups, Algorithms, and Programming, Version 4.12.2. 2022. https://www.gap-system.org/Contacts/cite.html |
| [7] | P.Heering, GAP4 code for chambers of PG \((3,q)\). https://github.com/PhilippHeering/Code_for_chambers_of_PG3q, 2023. |
| [8] | K.Metsch, How many \(s\)‐subspaces must miss a point set in \(PG(d,q)\), J. Geom. 86 (2006), no. 1-2, 154-164. · Zbl 1122.51008 |
| [9] | K.Metsch, The chromatic number of two families of generalized Kneser graphs related to finite generalized quadrangles and finite projective 3‐spaces, Electron. J. Combin. 28 (2021), no. 3, Paper No. 3.2, 12. · Zbl 1467.51006 |
| [10] | L. H.Soicher, GRAPE, graph algorithms using permutation groups, Version 4.9.0. Refereed GAP package. https://gap-packages.github.io/grape, December 2022. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
