The Circular Chromatic Number Of Three Kinds Of Special Graphs

The star chromatic number x*(G) of a graph G(sometimes it is also called circular chromatic number Xc(G)) is a natural generation of the chromatic number x(G) of a graph.It was first defined by Vince in [1].For two integers 1 ≤ d ≤ k,a (k, d)-coloring of a graph G is a coloring c of the vertices G with colors {0,1, 2, ...,k-1}such that (x,y) ∈ E(G) ≥ d ≤ |c(x)-c(y)| ≤ k-d.The star chromatic number is defined as Xc(G) = inf{k/d: there is a (k,d) -coloring of G and 2d ≤ k ≤ |V(G)|}.After this,X.Zhu gave it another equal definition-cicular chromatic number in [3]. For onenessly,this paper calls it cicular chromatic number.In this paper we discuss the circular chromatic number of planar graphs, Mycielski graphs and distance graphs. This paper includes five parts. Part one is an introduction which introduces the definition of the circular chromatic number and it's equal definition, and then it presents theories and conclusions cited later. Part two, three and four have made conclusions and evolutions about the circular chromatic number of planar graphs, Mycielski graphs and distance graphs. Specially,we construct some new kinds of planar graphs with circular chromatic number 3 or 4 based on the results which have been surveyed in part two.Part five is a prospect.which surveys some open questions about the circular chromatic number of these three kinds of special graphs.