Abstract
We show that the q-Kneser graph qK 2k:k (the graph on the k-subspaces of a 2k-space over GF(q), where two k-spaces are adjacent when they intersect trivially), has chromatic number q k + q k−1 for k = 3 and for k < q log q − q. We obtain detailed results on maximal cocliques for k = 3.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Blokhuis A., Brouwer A.E., Chowdhury A., Frankl P., Patkós B., Mussche T., Szőnyi T.: A Hilton-Milner theorem for vector spaces. Electr. J. Combin. 17, R71 (2010)
Eisfeld J., Storme L., Sziklai P.: Minimal covers of the Klein quadric. J. Combin. Theory Ser. A 95, 145–157 (2001)
Frankl P., Wilson R.M.: The Erdős-Ko-Rado theorem for vector spaces. J. Combin. Theory Ser. A 43, 228–236 (1986)
Godsil C.D., Newman M.W.: Independent sets in association schemes. Combinatorica. 26, 431–443 (2006)
Hsieh W.N.: Intersection theorems for systems of finite vector spaces. Discrete Math. 12, 1–16 (1975)
Mussche T.: Extremal combinatorics in generalized Kneser graphs, Ph.D. Thesis, Eindhoven University of Technology (2009).
Acknowledgments
Author A. Blokhuis acknowledges support from ERC grant DISCRETECONT 227701. This research began when T. Szőnyi was visiting Eindhoven University of Technology. The hospitality of TU/e and the financial support of EIDMA and Lex Schrijver’s Spinoza grant is gratefully acknowledged. Later T. Szőnyi was partly supported by OTKA Grant K 81310. In Spring 2004 the first author visited Günther Ziegler in Berlin. One of the problems he suggested to look at was determining the chromatic number of the q-Kneser graph.
Open Access
This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
Author information
Authors and Affiliations
Corresponding author
Additional information
This is one of several papers published together in “Design, Codes and Cryptography” on the special topic: “Combinatorics—A Special Issue Dedicated to the 65th Birthday of Richard Wilson.”
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Blokhuis, A., Brouwer, A.E. & Szőnyi, T. On the chromatic number of q-Kneser graphs. Des. Codes Cryptogr. 65, 187–197 (2012). https://doi.org/10.1007/s10623-011-9513-1
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-011-9513-1