Some Results On The Circular Chromatic Number And Circular Clique Number Of Graphs

A. Vince introduces X~*, the concept of star chromatic number in [18], a generalization of the chromatic number of a graph. Xuding Zhu in [22] introduces the circular chromatic number Xc and furthermore proves that Xc = X~* for any graph G. It is known [3, 18, 24] that X(G) - 1 < Xc(G) ≤ X(G) for any graph G. Xuding Zhu in [17] proves that critical graphs G with large girth have circular chromatic number Xc(G) colose to X(G) - 1 and constructs m-connected (m + 1)-critical graphs with Xc{G) arbitrarily colose to x(G) - 1. On the other hand, Zhu in [17] presents the following valuabe sufficient condition under which a graph G satisfies Xc(G) = x(G). Theorem A Suppose x(G) = n. If there is a non-trivial subset A of V (i.e., A ≠ V and A ≠ (?)) such that for any n-coloring c of G, each color class X of c is either contained in A or disjoint from A, then Xc(G) = X(G).From this theorem, we can see that if G has a vertice with degree |V(G)| - 1, then Xc(G) = x(G), which is equivalent to the following corollary in [24]. Corollary A If G has a universal vertex, then Xc(G) - X(G).In this article, we prove that if G has a vertice with degree |V(G)| - 2, then Xc(G) = X(G). This result is a corollary of the following theorem, a proposition in [6].Theorem B If Xc(G) = k/d, where gcd(k, d) = 1, then d(v) ≤ |V(G)| - 2d+1 for each v ∈ V(G).If G has a vertice with degree |V(G)| - 3, it is not necessary that Xc(G) = X(G). To obtain Xc(G) = X(G), we need to add some conditions on such graphs. The following theorem 2 is a sufficient condition satisfyingXc(G) = X(G).Theorem 1 Let Gbea graph on n vertices. If G has three vertices x, y, z such that {x, y, z} is an independent set and d(x) = n - 3, then Xc(G)=X(G).This article discusses graphs having two vertices with degree |V(G) | - 3 and declares that two kinds of those graphs have Xc(G) = x(G). Theresults are the following theorem 3 and theorem 4.Theorem 2 Let G be a graph on n vertices. If G has two vertices x, y such that d{x) — d(y) = n — 3, x is not adjacent to y and there is a vertice u adjacent to neither x nor y, then Xc{G) = x(G)-Obviously, this theorem is a corollary of theorem 1. Theorem 3 Let G be a graph on n vertices. If G has four vertices xp, xq, x, y such that d(xp) = d(xq) = n - 3 and {x, y} = V(G) \ {N(xp) U N(xq)),then Xc(G) = X(G).Genghua Fan in [6] studies the graphs with Xc(M(G)) = x(M(G)) and presents the following theorem.Theorem C Let G be a graph on n vertices. If G contains a K5 such that N(Ks) 7^ V(G) and each vertice of K§ has degree at least n — 3 in G, then Xc(M(G))=X(M(G)).We adjust this condition and acquire two main results: Theorem 4 Let G be a graph on n vertices. If G has different vertices xp, xq, xr, x3, x, y such that, d(xi) = n — 3(z G {p, q, r, s}) and {x, y} = V{G) \ U N(xt), then Xc(M(G)) = X(M(G)).ie{p,q,r,s}Theorem 5 Let G be a graph on n vertices. If G has a clique with order 3 and each vertice of the clique has degree n — 2, then Xc{M(G)) = x(M(G)).Besides the above graphs, we try the Kneser graphs to make their circular chromatic numbers equal chromatic numbers under the construction of Mycielski.Furthermore, for theorem 5, the condition order 3 can not be reduced since there is a graph G in § 2.3 which just has two adjacent vertices and the degree of each of them is n - 2, however Xc(M(G)) < x(Af(G)). The theorem 4 make us want to know whether the graph G in theorem 3 has Xc(M(G)) = x{M(G)). The answer is negative. But for some Kneser graphs G, both Xc(G) = *(G) and Xc(M(G)) = x(Af(G)). In [15] the following two kinds of Kneser graphs have the same circular chromatic number and chromatic number. Theorem D Xc(KG(m, 2)) = X{KG{m, 2)) for integer m > 4.Theorem E Xc(KG2(m, 2)) = X(KG2(m, 2)) for integer m > 4 and m^ 5.In this article we get the following main results about Kneser graphs under the construction of Mycielski.Theorem 6 Xc(M(KG(m, 2))) = X(M{KG{m, 2))) for the integer m > 16.Theorem 7 Xc{M(KG2{m, 2))) = X(M(KG2(m, 2))) for the integer m> 20.Questionl: Is it possible that the value of m can be reduced in theorem 6 and theorem 7?Question2: What determines Xc(M(G)) = X(M(G)) for G with Xc(G) = X(G)?Baogang Xu and Xinghe Zhou in [20] prove the following result about the circular clique number of G x H. Theorem F If uc{G) ^ 2 + |, then ljc(G x H) = max{wc(G), uc(H)}.This article certifies the following theorem. Theorem 8 uc(M(G)) = loc(G) for any graph G. Theorem 9 ujc(G H) = min{u;c(G), ujc(H)} for all graphs G and H.