Circular perfect graphs

The circular clique number of G is introduced in [Zhu05]:

            w_c(G) = max {p/q: K_{p/q} admits a homomorphism to G}. 

It is proved in [Zhu05] that w_c(G) = max {p/q: K_{p/q} is an induced subgraph G}.  It follows from the definitions that for any graph G,

w(G) \le w_c(G) \le \chi_c(G) \le \chi(G). 

A graph G is called circular perfect  [Zhu05]  if for any induced subgraph H of G, w_c(H) = \chi_c(H).  So perfect graphs are circular perfect. However, there are circular perfect graphs that are not perfect. For example, the circular clique (in particular, the odd cycles and their complements) are circular perfect.  The concept of circular perfect graphs is used in [Zhu01] and [Zhu03] to prove an analogue of Hajos Theorem for circular chromatic number of graphs.  However, little is known about the structure of circular perfect graphs.  The ultimate goal could be to characterize all circular perfect graphs.

Problem 1     Characterize circular perfect graphs.

However, this problem seems to be quite difficult. It is very likely that there is no simple forbidden structure characterization as that of perfect graphs.  There is no conjecture as to which graphs are circular perfect. 

By Perfect Graph Theorem, any minimal imperfect graph G has min { \alpha(G), \omega(G) } = 2. It was asked by Arnaud Pecher whether minimal circular imperfect graphs have bounded min {\alpha(G), \omega(G)}. This question is answered in the negative in [PanZhu08]

Baogang Xu proved that the line graph of a subcubic graph G is minimal circular imperfect if and only if the line graph of G is critical 4-chromatic. This implies that it is NP-hard to determine is a graph is minimal circular imperfect. Hence, it is NP-hard to determine if a graph is circular perfect. If one attempts to characterize circular perfect graphs, maybe it is best to start with special classes of graphs.

Problem 2  Characterize circular perfect planar graphs, or circular perfect series-parallel graphs.

Problem 3  What is the complexity to determine chi_c(G) if G is a circular perfect graph ?