# Graphclass: circular perfect

Definition:

For 1<=d<=k, let Kk/d be the graph with vertices 0,1...k-1 and edges ij iff d<=|i-j|<=k-d. For example, an odd-hole C2n+1 equals K(2n+1)/n and the co-cycle co-Cn equals Kn/2 .
A homomorphism from a graph G to a graph H is a mapping f:V(G)->V(H) such that f(x)f(y) \in E(H) whenever xy\in E(G).
The circular chromatic number \chi_c(G) of a graph G is the minimal k/d such that a homomorphism from G to Kk/d exists. In other words, \chi_c(G) is the minimal k/d for which a function f: V(G) -> {0,..,k-1} exist such that for adjacent vertices x,y: d<=|f(x)-f(y)|<=k-d.
The circular clique number \omega_c(G) of a graph G is the maximal k/d such that a homomorphism from Kk/d to G exists.
A graph is circular perfect if for every induced subgraph H, \chi_c(H) = \omega_c(H).

[1301] [1303]

## Inclusions

The map shows the inclusions between the current class and a fixed set of landmark classes. Minimal/maximal is with respect to the contents of ISGCI. Only references for direct inclusions are given. Where no reference is given, check equivalent classes or use the Java application. To check relations other than inclusion (e.g. disjointness) use the Java application, as well.

[+]Details

[+]Details

## Problems

3-Colourability Polynomial [+]Details
Clique Polynomial [+]Details
Clique cover Unknown to ISGCI [+]Details
Cliquewidth Unbounded [+]Details
Cliquewidth expression Unbounded or NP-complete [+]Details
Colourability Polynomial [+]Details
Cutwidth NP-complete [+]Details
Domination NP-complete [+]Details
Feedback vertex set NP-complete [+]Details
Hamiltonian cycle NP-complete [+]Details
Hamiltonian path NP-complete [+]Details
Independent set Unknown to ISGCI [+]Details
Recognition Unknown to ISGCI [+]Details
Treewidth NP-complete [+]Details
Weighted clique Unknown to ISGCI [+]Details
Weighted feedback vertex set NP-complete [+]Details
Weighted independent set Unknown to ISGCI [+]Details