ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 15 (2018) 161-172
https://doi.org/10.26493/1855-3974.1296.5c7
(Also available at http://amc-journal.eu)
Circular chromatic number of induced subgraphs of Kneser graphs*
Meysam Alishahi
School of Mathematical Sciences, Shahrood University of Technology, Shahrood, Iran
Ali Taherkhani t
Department of Mathematics, Institute for Advanced Studies in Basic Sciences (IASBS),
Zanjan 45137-66731, Iran
Received 17 January 2017, accepted 11 September 2017, published online 13 June 2018
Investigating the equality of the chromatic number and the circular chromatic number of graphs has been an active stream of research for last decades. In this regard, Hajiabolhassan and Zhu in 2003 proved that if n is sufficiently large with respect to k, then the Schrijver graph SG(n, k) has the same chromatic and circular chromatic number. Later, Meunier in 2005 and independently, Simonyi and Tardos in 2006 proved that x(SG(n, k)) = xc(SG(n, k)) if n is even. In this paper, we study the circular chromatic number of induced subgraphs of Kneser graphs. In this regard, we shall first generalize the preceding result to s-stable Kneser graphs for large even n and even s. Furthermore, as a generalization of the Hajiabolhassan-Zhu result, we prove that if n is large enough with respect to k, then any sufficiently large induced subgraph of the Kneser graph KG(n, k) has the same chromatic number and circular chromatic number.
Keywords: Chromatic number, circular chromatic number, Kneser graph, stable Kneser graph. Math. Subj. Class.: 05C15
*The authors would like to acknowledge Professor Hossein Hajiabolhassan for his invaluable comments and suggestions. They also thank the anonymous referees for all their remarks that helped in improving the presentation of the paper.
t Corresponding author
E-mail addresses: meysam_alishahi@shahroodut.ac.ir (Meysam Alishahi), ali.taherkhani@iasbs.ac.ir (Ali Taherkhani)
Abstract
©® This work is licensed under https://creativecommons.org/licenses/by/3.0/
162
Ars Math. Contemp. 15 (2018) 147-160
1 Introduction
Throughout the paper, the symbol [n] stands for the set {1,..., n}. Let n and d be two positive integers. The circular complete graph Kn is a graph with vertex set [n] and two vertices i and j are adjacent whenever d < |i - j| < n - d. For a graph G, the circular chromatic number of G, denoted by Xc(G), is defined as follows:
Xc(G) =f inf j n : there is a homomorphism from G to Kn j .
It is known that the infimum can be replaced by minimum. Moreover, one can see that x(G) - 1 < Xc(G) < x(G), see [36]. Therefore, the circular chromatic number is a refinement of the chromatic number. It is a natural question to ask for which graphs G, we have Xc(G) = x(G). However, it turns out to be a difficult question. Hell [19] proved that the problem of determining whether a graph has the circular chromatic number at most n is NP-Hard. Hatami and Tusserkani [18] showed that the problem of determining whether or not Xc(G) = x(G) is NP-Hard even if the chromatic number is known. Therefore, finding necessary conditions for graphs to have the same chromatic and circular chromatic number turns out to be an interesting problem. This problem has received significant attention, for instance see [1, 17, 36, 37].
For two positive integers n and k, where n > 2k, the Kneser graph KG(n, k) is a graph with vertex set ('k'), that is, the family of all k-subsets of [n], and two vertices are adjacent if their corresponding k-subsets are disjoint. Kneser in 1955 [23] conjectured that the chromatic number of KG(n, k) is n — 2k + 2. In 1978, Lovisz [26] gave an affirmative answer to Kneser's conjecture. He used algebraic topological tools, giving birth to the field of topological combinatorics. For a positive integer s, a nonempty subset S of [n] is said to be s-stable if for any two different elements i and j in S, we have s <|i - j | < n - s. Throughout the paper, the family of all s-stable k-subsets of [n] is denoted by ('k') s. The subgraph of KG(n, k) induced by all s-stable k-subsets of [n] is called the s-stable Kneser graph and is denoted by KGs (n, k). The 2-stable Kneser graph KG2 (n, k) is known as the Schrijver graph SG(n, k). Schrijver [31] proved that Schrijver graphs are vertex critical subgraphs of Kneser graphs with the same chromatic number. Meunier [30] showed that for any two positive integers n and k, where n > sk, the s-stable Kneser graph KGs (n, k) can be colored by n - s(k -1) colors and conjectured that the chromatic number is n - s (k -1). Jonsson [22] proved that this conjecture is true provided that s > 4 and n is sufficiently large with respect to k and s. Also, Chen [12] confirmed Meunier's conjecture for even values of s.
Lovisz's theorem [26] has been generalized in several aspects. For a hypergraph H, the general Kneser graph KG(H) is a graph with vertex set E(H) and two vertices are adjacent if their corresponding edges are vertex disjoint. Dol'nikov [13] generalized Lovisz's result and proved that the chromatic number of KG(H) is at least the colorability defect of H, denoted by cd(H), where the colorability defect of H is the minimum number of vertices which should be excluded from H so that the induced subhypergraph on the remaining vertices is 2-colorable.
For a vector X = (xi,...,xn) G {-, 0, +}n, a sequence xHl , xi2 , ...,xit (ii < • • • < it) is called an alternating subsequence of X with length t if Xj = 0 for each j G {1,..., t} and Xj. = xij+1 for each j G {1,..., t - 1}. The maximum length of an alternating subsequence of X is called the alternation number of X, denoted by alt(X). For 0 =f (0,..., 0), we define alt(0) =f 0. Also, we define X + and X- to be respectively
M. Alishahi and A. Taherkhani: Circular chromatic number of induced subgraphs ofKneser... 
163
the indices of positive and negative coordinates of X, i.e.,
X + =f {i : xj = +} and X- =f {i : xj = -}.
Note that both X + and X- are subsets of [n] and by abuse of notation, we can write
X = (X +, X-). For two vectors X, Y e {-, 0, +}n, by X C Y, we mean X + C Y+ and X - C Y -.
Let H = (V, E) be a hypergraph and a : [n] —> V(H) be a bijection. The alternation number of H with respect to a, denoted by altCT(H), is the maximum possible value of an alt(X) such that E(H[a(X +)]) = E(H[a(X-)]) = 0. Also, the strong alternation number of H with respect to a, denoted by saltCT (H), is the maximum possible value of an alt(X) such that E(H[a(X +)]) = 0 or E(H[a(X-)]) = 0. The alternation number of H, denoted by alt(H), and the strong alternation number of H, denoted by salt(H), are respectively the minimum values of altCT (H) and saltCT(H), where the minimum is taken over all bijections a : [n] —> V(H). The present first author and Hajiabolhassan [4] proved the following theorem.
Theorem A. For any hypergraph H, we have
x(KG(H)) > max{|V(H)| - alt(H), |V(H)| - salt(H) + 1} .
One can simply see that this result improves the aforementioned Dol'nikov's result [13]. Using this lower bound, the chromatic number of several families of graphs is computed, for instance see [2, 3, 5, 6, 8].
In 1997, Johnson, Holroyd, and Stahl [21] proved that Xc(KG(n, k)) = x(KG(n, k)) provided that 2k +1 < n < 2k + 2 or k = 2. They also conjectured that the circular chromatic number of Kneser graphs is always equal to their chromatic number. This conjecture has been studied in several articles. Hajiabolhassan and Zhu [17] using a combinatorial method proved that if n is large enough with respect to k, then xc(KG(n, k)) = x(KG(n, k)). Later, using algebraic topology, Meunier [29] and Simonyi and Tardos [33] independently confirmed this conjecture for the case of even n. It should be mentioned that the results by Hajiabolhassan and Zhu [17], Meunier [29], and Simonyi and Tardos [33] are indeed proved for the Schrijver graph SG(n, k). Eventually in 2011, Chen [11] confirmed the Johnson-Holroyd-Stahl conjecture. Chen's proof was simplified by Chang, Liu and Zhu in [10] and by Liu and Zhu in [25]. The present first author, Hajiabolhassan, and Meunier [8] generalized Chen's result to a larger family of graphs. They introduced a sufficient condition for a hypergraph H having x(KG(H)) = Xc(KG(H)).
Plan. The paper contains two main sections. In Section 2, we shall investigate the coloring properties of stable Kneser graphs. In this regard, we prove the equality of the chromatic number and the circular chromatic number of s-stable Kneser graph KGs(n, k) provided that n > (s + 2)k - 2 and both n and s are even. In the last section, we study the circular chromatic number of large induced subgraphs of Kneser graphs. Indeed, it is proved that, for large enough n, any sufficiently large induced subgraph of the Kneser graph KG(n, k) has the same chromatic number and circular chromatic number. In particular, giving a partial answer to a question posed by Lih and Liu [24], we present a threshold n(k, s) such that for any n > n(k, s), the chromatic number and circular chromatic number of KGs(n, k) are equal.
164
Ars Math. Contemp. 15 (2018) 147-160
2 Chromatic number of stable Kneser graphs
As it is mentioned in the previous section, the chromatic number of s-stable Kneser graph KGs(n, k) is determined provided that k and s > 4 are fixed and n is large enough [22] or s is even [12]. In this section, we first present a generalization of Theorem A. Using this generalization, for any even s, we prove that any proper coloring of s-stable Kneser graph KGs(n, k) contains a large colorful complete bipartite subgraph, which immediately gives solutions to the chromatic number of s-stable Kneser graphs KGs(n, k). Also, this result concludes that the circular chromatic number of s-stable Kneser graph KGs(n, k) equals to its chromatic number provided that n > (s + 2)k - 2 and both n and s are even.
Tucker's lemma is a combinatorial counterpart of the Borsuk-Ulam theorem with several useful applications, for instance, see [27, 28].
Lemma A (Tucker's lemma [35]). Let A: {-, 0, +}n \ {0} —> {±1,..., ±m} be a map satisfying the following properties:
•	it is antipodal: A(—X) = —A(X) for each X g {—, 0, +}n \ {0}, and
•	it has no complementary edges: there are no X and Y in {-, 0, +}n \ {0} such that
X C Y and A(X) = —A(Y).
Then m > n.
There are several results concerning the existence of a large complete bipartite multicolored subgraph in any proper coloring of a graph G, see [4, 11, 32, 33, 34]. In what follows, we present a similar type of result with a combinatorial proof. Note that since there is a purely combinatorial proof [28] for Tucker's lemma, any proof using Tucker's lemma with combinatorial approach can be considered as a purely combinatorial proof.
Theorem 2.1. Let H be a hypergraph and set t = max {|V(H)| — alt(H), |V(H)| — salt(H) +1}. For any proper coloring c: V(KG(H)) —> [C], there exists a complete bipartite subgraph Kyt/2j,[t/2] of KG(H) whose vertices receive different colors and moreover, these different colors occur alternating on the two parts of the bipartite graph with respect to their natural order.
Proof. Let 01,02: [n] —> V(H) be two bijections for which we have alt(H) = altCTl (H) and salt(H) = saltCT2 (H). Now, we shall proceed the proof with two different cases, t = n—alt(H) and t = n—salt(H) + 1. Assume thatt = n—alt(H) (resp. t = n—salt(H) + 1). For simplicity of notation, by identifying the set V(H) and [n] via the bijection o1 (resp.
0-2), we may assume that V(H) = [n]. For each X = (X +, X-) g {—, 0, +}n \ {0}, define c (X) = (c(X +) , c(X )) g {—, 0, +}C to be a signed vector, where
c(X +) d=f {c(e) : e G E(H) and e C X +}
and
c(X-) d=f {c(e) : e G E(H) and e C X"} . For each X g {—, 0, +}n \ {0}, define A(X) as follows.
•	If alt(X) < altCTl (H) (resp. alt(X) < saltCT2 (H)), then define A(X) = ± alt(X), where the sign is positive if the first nonzero term of X is positive and is negative otherwise.
M. Alishahi and A. Taherkhani: Circular chromatic number of induced subgraphs ofKneser... 
165
• If alt(X) > altff1 (H) + 1 (resp. alt(X) > saltff2 (H) + 1), then define A(X) = ±(altff1 (H) + alt(c(X))) (resp. A(X) = ±(saltff2 (H) + alt(c(X)) -1)), where the sign is positive if the first nonzero term of c(X) is positive and is negative otherwise.
One can simply check that A satisfies the conditions of Lemma A. Consequently, there should be an X G {-, 0, +}n \ {0} such that |A(X)| = A(X) > n. Clearly, we should have alt(X) > altCT( (H) + 1 (resp. alt(X) > saltCT2 (H) + 1). Therefore, the definition of A(X) implies that alt(c(X)) > n - altCT( (H) (resp. alt(c(X)) > n - saltCT2(H) + 1). Let Z = (Z+, Z-) C c(X) be a signed vector such that alt(Z) = |Z| = t, as alt(c(X)) > t. Note that if Z+ U Z- = {n, i2,..., it}, where 1 < i1 < • • • < it < C, then we should have Z + = {ij : j g [t] is odd} and Z- = {ij : j g [t] is even}. For an j g [t], if j is odd (resp. even), then according to the definition of c(X), there is an edge e g E(H) such that e C X + (resp. e C X-) with c(e) = ij. Note that the induced subgraph of KG(H) on the vertices {e1,..., et} contains the desired complete bipartite graph.	□
Note that the complete bipartite graph whose existence is guaranteed by Theorem 2.1 is not necessarily an induced subgraph. Also, it is worth mentioning that we here used Tucker's lemma though, in case t = |V(H)| - alt(H), the previous theorem was proved in [4] by use of Ky Fan's lemma [14].
Let n, k, and s be positive integers, where n > sk and s is even. It is not difficult to see that if n is large enough (with respect to s and k), then any 2-stable (f (k - 1) + 1)-subset of [n] contains an s-stable k-subset of [n]. In the following two lemmas, we shall prove that n > (s + 2)k - 2 would be sufficient for this observation.
Lemma 2.2. Let s be an even positive integer and let n = 2s + 2. If S is a 2-stable subset of [n] of cardinality f + 1, then there are a, a' G S such that a - a' G {s, s + 1, s + 2}.
Proof. Without loss of generality, we may assume that 1 G S and 2s + 2 G S .If s + 1 G S, then there is nothing to prove. Therefore, let s + 1 G S. For 1 < i < f, define B =
{2i - 1,2i, 2i + s, 2i + s + 1}. Therefore, for some i, 1 < i < §, |Bj n S| = 2. Let a, a' G Bi n S, since S is 2-stable, we have a - a' G {s, s + 1, s + 2}.	□
Lemma 2.3. Let k and n be two positive integers and let s be an even positive integer, where n > (s + 2)k - 2. If S is a 2-stable subset of [n] of cardinality f(k - 1) + 1, then there is an s-stable k-subset of S. In particular, salt ([n], (k)§) = s(k - 1) + 1.
Proof. First note that for given k and s, if the statement is true for some n > k(s + 2) - 2, then it is true for all integers n' > n. Therefore it is enough to prove the lemma for n =
k(s + 2) - 2.
We use induction on k to prove the lemma. The validity of the lemma when k = 1 is trivial and when k = 2 it was shown in Lemma 2.2. Thus, we may assume that k > 3.
If for each i G S, we have {i + s, i + s + 1, i + s + 2}nS = 0 (where addition is modulo n), then we can greedily find an s-stable k-subset, and there is nothing to prove. Otherwise, without loss of generality, assume that n — s — 1 G S and n — 1, n, 1 G S.
Set An-s-1 = {n - s - 1, n - s,..., n}. Note that since n - 1, n G S, we have |An-s-1 nS| = § - p, for some 0 < £ < §. Now, consider [n] \	and S\	.
Set n = n - (s + 2) and S = S \ An_s_ 1. Note that [n] and [n] \ An_s_ 1 are equal and since 1 G S, S is a 2-stable subset of [n] of cardinality § (k - 2) + p +1.
166
Ars Math. Contemp. 15 (2018) 147-160
Define the s-subset B of [n] by
B = {n - 2s - 1, n - 2s,. .., n - s - 2}. By induction, we may consider the following two cases:
(i)	There is an s-stable (k - 1)-subset of S, say D, which has no element of B. In this case, it is readily verified that D = D U {n - s - 1} is an s-stable k-subset of [n], completing the proof in this case.
(ii)	There are at least fi + 1 s-stable (k - 1)-subsets of S, say Di, D2,..., Dsuch that each Dj has exactly one distinct element of B, say bj.
Now, consider the 2-stable subset {b1, b2,..., b^+1} U (Sn	), by Lemma 2.2,
there exist two elements a, b such that a - b e {s, s + 1, s + 2}. Since n - 1, n e S, both a, b are not in	. Hence, we may assume that a e An-s-1 and b = bj for some i,
1 < i < fi + 1. Let d be the smallest element of DDj. Since Dj is an s-stable (k - 1)-subset of [n], therefore we have s < b - d < n - s = n - (2s + 2). On the other hand, s < a - b < s + 2. Therefore, 2s < a - d < n - s. Therefore, Dj U {a} is an s-stable k-subset of [n] as desired.
Note that for an X e {-, 0, +}n \ {0} with alt(X) > s(k - 1) + 2, both X + and X- contain 2-stable subsets of size at least § (k - 1) + 1, which implies that both X+ and X- contain s-stable subsets of size at least k. This concludes that salt ([n], (k)s) = s(k - 1) + 1.	S □
We remind the reader that Meunier [30] showed that KGs (n, k) has a proper coloring with n - s(k - 1) colors. Note that if we set H = ([n], ([k])s), then KG(H) = KGs(n, k). Clearly, using these observations, Lemma 2.3, and Theorem 2.1, we have the next theorem.
Theorem 2.4. Let k and n be two positive integers and let s be an even positive integer, where n > (s + 2)k - 2. Any properly colored KGs(n, k) contains a complete bipartite subgraph K^i/2j,pi/2], where t = n - s(k - 1) such that all vertices of this subgraph receive different colors and these different colors occur alternating on the two parts of the bipartite graph with respect to their natural order. In particular, we have x(KGs(n, k)) = n - s(k - 1).
Let r be a positive integer. For an r-coloring c of a given graph G, a cycle C = v1, v2,..., vm, v1 is called tight if for each i e [m], we have c(vj+1) = c(vj) +1 (mod r). It is known [36] that Xc(G) = r if and only if the graph G is r-colorable and every r-coloring of G contains a tight cycle. In view of this result, to prove the next theorem, it suffices to show that any proper (n - s(k - 1))-coloring of KGs(n, k) contains a tight cycle.
Theorem 2.5. Let n, k, and s be positive integers, where n and s are even and n > (s + 2)k - 2. Then, we have
Xc(KGs(n,k)) = n - s(k - 1).
Proof. For simplicity of notation, we set t = n - s (k -1). In view of the former discussion, to prove the assertion, let c be a proper t-coloring of KGs(n, k). Consider the complete bipartite subgraph Kt/2,t/2 of KGs(n, k), whose existence is ensured by Theorem 2.4. Clearly, this subgraph contains a tight cycle, which completes the proof.	□
M. Alishahi and A. Taherkhani: Circular chromatic number of induced subgraphs ofKneser... 
167
The original proof of Lovisz of Kneser's conjecture is rather long and complicated [26]. B^riny [9], using Gale's lemma [15], presented a short proof of this result. For n > 2k, Gale [15] proved that the set [n] can be identified with a subset of Sn-2k in such a way that any open hemisphere contains at least one k-subset of [n] (a vertex of KG(n, k)). Schrijver [31] generalized Gale's lemma to 2-stable k-subsets of [n]. He also used this generalization to prove that x (SG(n, k)) = n - 2k + 2. For an interesting proof of Gale's lemma, see [16]. Moreover, the present first author and Hajiabolhassan [7] generalized Gale's lemma. For any hypergraph H = (V, E), they introduce a lower bound for the maximum possible value of m for which there is a subset X of Sm and a suitable identification of V with X such that any open hemisphere of Sm contains an edge of H. The next lemma can be obtained directly from this result. However, for the sake of completeness, we prove it here with a different approach.
Lemma 2.6. Let k and n be two positive integers and let s be an even positive integer, where n > (s + 2)k — 2. There exists an n- subset X of Sn-s(k-i)-2 and a suitable identification between X and [n] such that every open hemisphere of Sn-s(k-1)-2 contains an s-stable k-subset of [n].
Proof. Set p = § (k — 1) + 1. In view of the generalization of Gale's lemma by Schrijver [31], there exists an n-subset X of Sn-2p and an identification of X with [n] such that any open hemisphere of Sn-2p contains a 2-stable p-subset of [n]. Now, by Lemma 2.3, any 2-stable p-subset contains an s-stable k-subset. This implies that any open hemisphere of Sn-s(k-1)-2 contains an s-stable k-subset of [n] as desired.	□
Simonyi and Tardos [34], using the Tucker-Bacon lemma (Lemma B), proved that if the chromatic number of a graph G equals to a topological lower bound for chromatic number, then for any optimal coloring of G with colors [C] and for any partition L i±i M of [C], there is a multi-colored complete bipartite subgraph K|L|,|M| of G such that all colors in L are assigned to the vertices of one side of K|L|,|M| and all colors in M are assigned to the vertices of the other side. These kinds of results are known as m type theorems, see [32, 34].
Lemma B (Tucker-Bacon lemma). Let U1, U2,..., Ud+2 be open subsets of the d-sphere Sd such that for any 1 < i < d + 2, U n — U = 0 and also, U1 U • • • U Ud+2 = Sd. Then for any partition A U B = {1, 2,..., d + 2} for which A = 0 and B = 0, there is an x G Sd such that x G nieAUj and — x G nj£B Uj.
In what follows, similar to the Simonyi-Tardos result, using the Tucker-Bacon lemma, we prove a m type theorem for s-stable Kneser graphs provided that n is large and s is even.
Theorem 2.7. Let n, k, and s be positive integers, where s is even and n > (s + 2)k — 2. Also, let c be a proper coloring of KGs(n, k) with colors {1, 2,..., n — s(k — 1)} and assume that A and B form a partition of {1,2,..., n — s(k — 1)}. Then there exists a complete bipartite subgraph K;,m of KGs(n, k) with parts L and M such that |L| = l = | A |, |M | = m = |B| and the vertices in L and M receive different colors from A and B, respectively.
Proof. By Lemma 2.6, we can identify [n] with a subset of Sn-s(k-1)-2 such that every open hemisphere of Sn-s(k-1)-2 contains an s-stable k-subset of [n]. For 1 < i <
168
Ars Math. Contemp. 15 (2018) 161-172
n — s(k — 1), define
Ui = jx € Sn-s(k-1)-2 : H(x) contains a vertex with color i j .
One can see that each Ui is an open set, U1, U2,..., Un-s(k-1) covers sn-s(k-1)-2 and also none of them contains a pair of antipodal points. Thus, the Tucker-Bacon lemma implies that there is an x € gn-s(fc-1)-2 such that x € nieAUi and —x € njeB Uj. Therefore, in view of the definition of Ui's, for each i € A (resp. j € B), there is an s-stable k-subset Li (resp. Mj) of [n] such that c(Li) = i and Li C H(x) (resp. c(Mj) = j and Mj C H(—x)). Note that since H(x) n H(—x) = 0, for each i € A and j € B, Li is adjacent to Mj in KGs (n, k), which completes the proof.	□
We would like to mention that the idea of our proof is close to the Biriny's proof of Kneser conjecture [9].
3 Circular coloring of induced subgraphs of Kneser graphs
The concept of free coloring of graphs was introduced in [1] by the present first author and Hajiabolhassan as a tool for studying the circular chromatic number of graphs. Indeed, they proved that if the free chromatic number of a graph G is at least twice of its chromatic number, then x(G) = Xc(G).
An independent set in a graph G is called a free independent set if it can be extended to at least two distinct maximal independent sets in G. Clearly, one can see that an independent set F in G is a free independent set if and only if there exists an edge uv € E (G) such that (N(u) U N(v)) n F = 0. The maximum possible size of a free independent set in G is denoted by a(G). Furthermore, a vertex of a graph G is contained in a free independent set if and only if the graph obtained by deleting the closed neighborhood of this vertex has at least one edge (for more details, see [1]). As a natural extension of the chromatic number, we can define the free chromatic number of graphs as follows.
Definition 3.1. The free chromatic number of a graph G, denote ^>(G), is the minimum size of a partition of V(G) into free independent sets. If G does not have such a partition, then we set ^(G) = to.
The next lemma plays a key role in the rest of the paper.
Lemma C ([1, Lemma 2]). Let G be a graph such that Xc(G) = d with gcd(n, d) = 1. If d > 2, or equivalently, if Xc(G) = x(G), then ^(G) < 2x(g) — 1.
Let G be a graph with at least one free independent set. By definition, we have ^(G) > |V(G)|/a(G). It was proved by Hilton and Milner [20] that if T is an independent set of
KG(n, k) of size at least
then
n — 1\ in — k — 1 k — 1 — k — 1
n a=iii,
AeT
+ 2,
M. Alishahi and A. Taherkhani: Circular chromatic number of induced subgraphs ofKneser... 
169
for some i £ [n]. By using this result of Hilton and Milner, it was proved by Hajiabolhassan and Zhu in [17] that if n > 2k2(k - 1), then xc(KG(n, k)) = x(KG(n, k)). This result was improved in [1] by proving that we have xc(KG(n,k)) = x(KG(n, k)) for n > 2k2(k - 1) - 2k + 3. It was also showed in [17] that there is a threshold n(k) such that for n > n(k), we have xc(SG(n, k)) = x(SG(n, k)). This gave a positive answer to a question of Lih and Liu [24]. Lih and Liu [24] also posed the question of what is the smallest value of n(k). They proved that n(k) > 2k + 2. One should note that in [17] only the existence of the threshold n(k) is ensured and the authors did not present any upper bound for it.
Using the Hilton-Milner theorem, one can simply see that, for n > 2k, the size of any free independent set in the Kneser graph KG(n, k) is at most - ("—) < k(n-2), see [1]. In view of this observation, we generalize the result by Hajiabolhassan and Zhu [17] to the following theorem.
Theorem 3.2. Let n and k be two positive integers, where n > 2k2 (k - 1). Let H be an induced subgraph of KG(n, k) with at least 2k (k) vertices. Then H has the same chromatic number and circular chromatic number.
Proof. Obviously, the assertion holds for k = 1. So, let k > 2. Assume that H is an induced subgraph of KG(n, k) with at least 2k2(nk-1) (k) vertices. According to Lemma C, it is enough to show that ¿(H) > 2x(H). To this end, note that
|V (H )| a(H)
|V (H )| a(KG(n,k))
2k2(k-1) (n) n ) k)
k(n-2)
2k2(k - 1)n(n - 1) nk2 (k - 1)
therefore ¿(H) > 2n - 2 > 2x(KG(n, k)) > 2x(H) as desired.	□
In the rest of this section, we will return to the study of s-stable Kneser graphs from Section 2, KGs(n, k), but this time we consider KGs(n, k) as an induced subgraph of KG(n, k). We focus on the chromatic number and the circular chromatic number of the s-stable Kneser graph KGs (n, k). As a special case of the previous theorem, we introduce a threshold n(k, s) such that for any n > n(k, s), we have x(KGs(n, k)) = xc(KGs(n, k)). In this regard, we first need to count the number of vertices of KGs(n, k).
Let Ni be the number of vertices of KGs (n, k) containing i. It is obvious that Ni = Nj for all i, j £ [n]. Also, let A = {x1,..., xk} be a vertex of KGs(n, k), where 1 = x1 < x2 < • • • < xk < n. Define yi = xi+1 - xj for all 1 < i < k - 1 and yk = n - xk + 1. Since A g V(KGs(n, k)) and 1 £ A, we have y» > s for all i £ [k]. Also, since y1 + y2 + • • • + yk = n, any vertex A of KGs (n, k) with 1 £ A leads us to a solution of the following system:
Z1 + Z2 +-----+ Zk = n
Zi > s for each i £ [n]
¿(H) >
>
>
170
Ars Math. Contemp. 15 (2018) 147-160
and vise versa. Note that the number of solutions of the preceding system is (n	•
Consequently, for each i e [n], we have N, = N = i"-^-^-1) for all i e [n]. By an easy double counting, one can see that
|V(KG.(n,k))| = k ± N, = n (n - 'k8;/' - 1
i=1 V
Theorem3.3. Ifn > 2k2(k-1)+(s-1)k(k-1)+1, thenxc(KGs(n,k)) = x(KGs(n,k)).
Proof. Let X be the number of (k-1)-subsets B of the set [n-1] such that B n[(s-1)k] = 0, i.e.,
X = # {B : B C [n - 1] and B n [(s - 1)k] = 0} .
Obviously, we have (k-1) = (n-(sfcl11)fc-i) + X. On the other hand, one can check that X < (s - 1)k(k-2), which implies the following inequalities:
|V (KG,(»,k))| = n (n - kk*-1) -1
n n 1	n 2
>	kU-i- (s - 1)^(k- 2
n	/ n _2
>	i(i-T) <n -1 - (s - 1)k<k - 1»Kk - 2
Clearly, the previous inequalities lead us to the following:
|V(KGs(n, k))| a(KGs(n, k))
^ (n - 1 - (s - 1)k(k - 1)) (n-2)
^(KGs(n,k)) >
>
k( k-22)
> k^y (n - 1 - (s - 1)k(k - 1)).
Consequently, we have ^>(KGs(n, k)) > 2n > 2(n - s(k - 1)) provided that n > 2k2(k -1) + (s - 1)k(k - 1) + 1. Considering Lemma C, the proof is completed.	□
Note that for s = 2, the previous theorem gives an upper bound for the smallest value of the threshold n(k), giving a partial answer to the question posed by Lih and Liu [24].
References
[1]	M. Alishahi and H. Hajiabolhassan, Circular coloring and Mycielski construction, Discrete Math. 310 (2010), 1544-1550, doi:10.1016/j.disc.2010.01.019.
[2]	M. Alishahi and H. Hajiabolhassan, Hedetniemi's conjecture via altermatic number, 2014, arXiv:1403.4404 [math.CO].
[3]	M. Alishahi and H. Hajiabolhassan, On chromatic number and minimum cut, 2014, arXiv:1407.8035 [math.CO].
[4]	M. Alishahi and H. Hajiabolhassan, On the chromatic number of general Kneser hypergraphs, J. Comb. Theory Ser. B 115 (2015), 186-209, doi:10.1016/j.jctb.2015.05.010.
M. Alishahi and A. Taherkhani: Circular chromatic number of induced subgraphs ofKneser... 171
[5]	M. Alishahi and H. Hajiabolhassan, On the chromatic number of matching graphs, 2015, arXiv:1507.08456 [math.CO].
[6]	M. Alishahi and H. Hajiabolhassan, Chromatic number via Turdn number, Discrete Math. 340 (2017), 2366-2377, doi:10.1016/j.disc.2017.05.010.
[7]	M. Alishahi and H. Hajiabolhassan, A generalization of Gale's lemma, J. Graph Theory 88 (2017), 337-346, doi:10.1002/jgt.22215.
[8]	M. Alishahi, H. Hajiabolhassan and F. Meunier, Strengthening topological colorful results for graphs, European J. Combin. 64 (2017), 27-44, doi:10.1016/j.ejc.2017.03.011.
[9]	I. Birdny, A short proof of Kneser's conjecture, J. Comb. Theory Ser. A 25 (1978), 325-326, doi:10.1016/0097-3165(78)90023-7.
[10]	G. J. Chang, D. D.-F. Liu and X. Zhu, A short proof for Chen's alternative Kneser coloring lemma, J. Comb. Theory Ser. A 120 (2013), 159-163, doi:10.1016/j.jcta.2012.07.009.
[11]	P.-A. Chen, A new coloring theorem of Kneser graphs, J. Comb. Theory Ser. A 118 (2011), 1062-1071, doi:10.1016/j.jcta.2010.08.008.
[12]	P.-A. Chen, On the multichromatic number of s-stable Kneser graphs, J. Graph Theory 79 (2015), 233-248, doi:10.1002/jgt.21826.
[13]	V. L. Dol'nikov, A certain combinatorial inequality, Sib. Math. J. 29 (1988), 375-379, doi: 10.1007/bf00969645.
[14]	K. Fan, A generalization of Tucker's combinatorial lemma with topological applications, Ann. Math. 56 (1952), 431-437, doi:10.2307/1969651.
[15]	D. Gale, Neighboring vertices on a convex polyhedron, in: H. W. Kuhn and A. W. Tucker (eds.), Linear Inequalities and Related Systems, Princeton University Press, Princeton, New Jersey, volume 38 of Annals ofMathematics Studies, pp. 255-263, 1956.
[16]	C. Godsil and G. F. Royle, Algebraic Graph Theory, volume 207 of Graduate Texts in Mathematics, Springer-Verlag, New York, 2001, doi:10.1007/978-1-4613-0163-9.
[17]	H. Hajiabolhassan and X. Zhu, Circular chromatic number of Kneser graphs, J. Comb. Theory Ser. B 88 (2003), 299-303, doi:10.1016/s0095-8956(03)00032-7.
[18]	H. Hatami and R. Tusserkani, On the complexity of the circular chromatic number, J. Graph Theory 47 (2004), 226-230, doi:10.1002/jgt.20022.
[19]	P. Hell and J. Nesetril, On the complexity of H-coloring, J. Comb. Theory Ser. B 48 (1990), 92-110, doi:10.1016/0095-8956(90)90132-j.
[20]	A. J. W. Hilton and E. C. Milner, Some intersection theorems for systems of finite sets, Quart. J. Math. 18 (1967), 369-384, doi:10.1093/qmath/18.1.369.
[21]	A. Johnson, F. C. Holroyd and S. Stahl, Multichromatic numbers, star chromatic numbers and Kneser graphs, J. Graph Theory 26 (1997), 137-145, doi:10.1002/(sici)1097-0118(199711)26: 3<137::aid-jgt4>3.3.co;2-x.
[22]	J. Jonsson, On the chromatic number of generalized stable Kneser graphs, 2012, manuscript, https://people.kth.se/~jakobj/doc/submitted/stablekneser.pdf.
[23]	H. Kneser, Aufgabe 300, Jahresbericht der Deutschen Mathematiker-Vereinigung 51 (1941), 3 (II. Abteilung), https://gdz.sub.uni-goettingen.de/id/PPN37 721857X_ 0051.
[24]	K.-W. Lih and D. D.-F. Liu, Circular chromatic numbers of some reduced Kneser graphs, J. Graph Theory 41 (2002), 62-68, doi:10.1002/jgt.10052.
[25]	D. D.-F. Liu and X. Zhu, A combinatorial proof for the circular chromatic number of Kneser graphs, J. Comb. Optim. 32 (2016), 765-774, doi:10.1007/s10878-015-9897-3.
172
Ars Math. Contemp. 15 (2018) 147-160
[26]	L. Loväsz, Kneser's conjecture, chromatic number, and homotopy, J. Comb. Theory Ser. A 25 (1978), 319-324, doi:10.1016/0097-3165(78)90022-5.
[27]	J. Matousek, Using the Borsuk-Ulam Theorem, Universitext, Springer-Verlag, Berlin, 2003, doi:10.1007/978-3-540-76649-0.
[28]	J. Matousek, A combinatorial proof of Kneser's conjecture, Combinatorica 24 (2004), 163170, doi:10.1007/s00493-004-0011-1.
[29]	F. Meunier, A topological lower bound for the circular chromatic number of Schrijver graphs, J. Graph Theory 49 (2005), 257-261, doi:10.1002/jgt.20079.
[30]	F. Meunier, The chromatic number of almost stable Kneser hypergraphs, J. Comb. Theory Ser. A 118 (2011), 1820-1828, doi:10.1016/j.jcta.2011.02.010.
[31]	A. Schrijver, Vertex-critical subgraphs of Kneser graphs, Nieuw Arch. Wisk. 26 (1978), 454-461, https://research.tue.nl/en/publications/ vertex-critical-subgraphs-of-kneser-graphs.
[32]	G. Simonyi, C. Tardif and A. Zsbän, Colourful theorems and indices of homomorphism complexes, Electron. J. Combin. 20 (2013), #P10, http://www.combinatorics.org/ ojs/index.php/eljc/article/view/v2 0i1p10.
[33]	G. Simonyi and G. Tardos, Local chromatic number, Ky Fan's theorem and circular colorings, Combinatorica 26 (2006), 587-626, doi:10.1007/s00493-006-0034-x.
[34]	G. Simonyi and G. Tardos, Colorful subgraphs in Kneser-like graphs, European J. Combin. 28 (2007), 2188-2200, doi:10.1016/j.ejc.2007.04.015.
[35]	A. W. Tucker, Some topological properties of disk and sphere, in: Proceedings of the First Canadian Mathematical Congress, Montreal, 1945, University of Toronto Press, Toronto, pp. 285-309, 1946.
[36]	X. Zhu, Circular chromatic number: a survey, Discrete Math. 229 (2001), 371-410, doi:10. 1016/s0012-365x(00)00217-x.
[37]	X. Zhu, Recent developments in circular colouring of graphs, in: M. Klazar, J. Kratochvil, M. Loebl, J. Matousek, R. Thomas and P. Valtr (eds.), Topics	in Discrete Mathematics, Springer, Berlin, volume 26 of Algorithms and Combinatorics,	pp. 497-550, 2006, doi: 10.1007/3-540-33700-8_25.