Circular perfect graphs (Q4667799)

For \(1\leq d\leq k\) let \(K_{k/d}\) be the graph with vertex set \(\{0,\dots,k-1\}\) and edge set \(\{ij: d\leq|i-j|\leq k-d\}\). The circular chromatic number of a graph \(G\) is the minimum of those \(k/d\) for which \(G\) admits a homomorphism to \(K_{k/d}\). The circular clique number \(\omega_c(G)\) is the maximum of those \(k/d\) for which \(G\) admits a homomorphism to \(K_{k/d}\). \(G\) is called circular perfect, if for every induced subgraph \(H\) of \(G\) we have \(\chi_c(H)= \omega_c(H)\). It is shown that (i) if \(G\) is circular perfect, then for every vertex \(x\) of \(G\), \(N[x]\) \((= N(x)\cup\{x\})\) is a perfect graph, and conversely, (ii) if for any vertex \(x\) of \(G\), \(N[x]\) is perfect and \(G- N[x]\) is bipartite with no induced \(P_5\), then \(G\) is circular perfect.