Polynomial time computability of some graph parameters for superclasses of perfect graphs (Q1758876)

\textit{X. Zhu} [J. Graph Theory 48, No. 3, 186--209 (2005; Zbl 1071.05037)] defined the circular chromatic number and the circular clique number of a graph and introduced circular-perfect graphs similar to perfect graphs. So far we do not have polynomial time algorithms computing these parameters, even if the inputs are restricted to circular perfect graphs. The authors restrict the inputs further to graphs \(G=(V,E)\) where \(G[N(v)]\) is perfect for every vertex \(v \in V\), and use polyhedral arguments to obtain polynomial time algorithms computing weighted versions of the circular chromatic number and the circular clique number.