The Study On The Kind Of Perfect Graph

Since the concept of the star chromatic number was introduced by A.Vince in 1988, a variety of research has been done on the star chromatic number and many new results and natural generalizations have been recieved. X.Zhu introduced the equivalent difinition of the star chromatic number, i.e. the circular chromatic number in 1992, and he proved two sufficent conditions of the circular perfect graph in 1999 where the circular perfect graph is the generalization of the perfect graph.In this paper we mainly study on the sufficent condition of the triangle free circular perfect graph. This result should be used to judge the circular perfect property of the triangle free graph and prove an anologue of Hajos theorem for the circular chromatic for 2 < k/d < 3. Namely we shall design a few graph operations and prove that for any 2 < k/d < 3. starting from the graph G^. one can contruct all graphs of circular number at least k/d by repeatedly applying these graph operations. This paper mainly improves the proof of X.Zhu on the sufficient condition of the triangle free circular perfect graph by choosing the maximum degree vertex x of G to analyze the structure of N[x] and circularly chosing the maximum degree vertex of G. Finally we can draw a conclusion: A graph is a Gkd if and only if G is triangle free core graph, for every x of G, G - N[x] is a bipartite graph which contains no induced Cn for n > 6, and every induced path of G - N[x] is well-linked.