Circular Chromatic Number And Circular Imperfect Graphs

The circular chromatic number of a graph is a natural generalization of the chromatic number of a graph introduced by Vince in 1988 under the name " the star chromatic number " . Zhu presented 3 operations [3] that do not decrease the circular chromatic number, these operations will be used to replace the Hajos' sum to construst all graphs of circular chromatic number at least k/d from copies of G_k^d , k/d ≥ 3. In this thesis , we construct a class of graphs which have the same circular chromatic number by zhu's 3 operations and calculate the circular clique number of the resulting graphs S₁, S₂, S₃[3]. Based on these results , we give some sufficient conditions for S₁, S₂, S₃[3] to be circular imperfect .At the same time , we present a simple proof of the following theorem [3] : if r ≥3 and G₁, G₂, ...... G₇ are graphs with circular chromatic number at least r ,then Xc(S₃) ≥ r . At last ,we give another equivalent definition for circular chromatic number : For any graph G, Xc(G) = min{k/d\2d ≤ k ≤| V(D) | and ξ_k,d(G) ≤ k/d}.( D is an orientation of G )...