SOME RESULTS ON CIRCULAR PERFECT GRAPHS AND PERFECT GRAPHS  

作　　者：XUBaogang 

机构地区：[1]SchoolofMathematicsandComputerScience,NanjingNormalUniversity,Nanjing210097China

出　　处：《Journal of Systems Science & Complexity》2005年第2期167-173,共7页系统科学与复杂性学报（英文版）

基　　金：This research is supported partially by National Natural Science Funds of China(10001035 and 10371055).

摘　　要：An r-circular coloring of a graph G is a map f from V(G) to the set of open unit intervals of an Euclidean circle of length r, such that f(u) ∩ f(v) = Ф whenever uv ∈ E(G). Circular perfect graphs are defined analogously to perfect graphs by means of two parameters, the circular chromatic number and the circular clique number. In this paper, we study the properties of circular perfect graphs. We give (1) a necessary condition for a graph to be circular perfect, (2) some circular critical imperfect graphs, and (3) a characterization of graphs with the property that each of their induced subgraphs has circular clique number the same as its clique number, and then the two conjectures that are equivalent to the perfect graph conjecture.

关 键 词：circular perfect PERFECT GRAPH 

分 类 号：O157.5[理学—数学]