On Chromatic Number of General Kneser Graphs

Sharareh Alipour, Amir Jafari


For integers $0 < i < k < n$, the general Kneser graph $K(n; k; i)$, is a graph
whose vertices are subsets of size $k$ of the set ${1, 2, ..., n:}$ and two vertices $F$ and $F'$ are connected if and only if their intersection has less than i elements. In this paper we study the chromatic number of this graph. Some new bounds
and properties for this chromatic number is derived.


Graph theory, Kneser Graph, Chromatic number

Full Text:



M. Aigner and G.M. Ziegler, Proofs from THE BOOK, 3 ed., Springer, 2004.

I. Barany, A short proof of Kneser's conjecture, J. Comb. Theory, Ser. A 25 (1978), no. 3, 325-326.

F.R.K. Chung and L. Lu, An upper bound for the Turan number t3(n; 4), J. Comb. Theory, Ser. A 87 (1999), no. 2, 381-389.

P. Frankl, On the chromatic number of the general Kneser-graph, J. Graph Theory 9 (1985), no. 2, 217-220.

J.E. Greene, A new short proof of Kneser's conjecture, Amer. Math. Monthly 109 (2002), no. 10, 918-920.

M. Kneser, Aufgabe360, Jahresber. Dtsch. Math.-Ver. 58 (1955), no. 1, 27-27.

A.V. Kostochka, A class of constructions for Turan's (3, 4) problem, Combinatorica 2 (1982), no. 2, 187-192.

L. Lovasz, Kneser's conjecture, chromatic number, and homotopy, J. Comb. Theory, Ser. A 25 (1978), no. 3, 319-324.

J. Matousek, Using the Borsuk-Ulam theorem, Springer-Verlag, 2003.

J. R. Tort, Un probleme de partition de l'ensemble des parties a trois elements d'un ensemble ni, Discrete Math. 44 (1983), no. 2, 181-185.

P. Turan, On an extremal problem in graph theory, Colloquium Mathematicae 13 (1964), no. 2, 251-254.

Contributions to Discrete Mathematics. ISSN: 1715-0868