circular perfect graphs

Definition:

For 1<=d<=k, let K_k/d be the graph with vertices 0,1...k-1 and edges ij iff d<=|i-j|<=k-d. For example, an odd-hole C_2n+1 equals K_(2n+1)/n and the co-cycle co-C_n equals K_n/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 K_k/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 K_k/d to G exists.
A graph is circular perfect if for every induced subgraph H, \chi_c(H) = \omega_c(H).

Input:	A graph G in this class.
Output:	True iff each vertex of G can be assigned one colour out of 3 such that whenever two vertices are adjacent, they have different colours.

Input:	A graph G in this class and an integer k.
Output:	True iff G contains a set S of pairwise adjacent vertices, with \|S\| >= k.

Input:	A graph G in this class and an integer k.
Output:	True iff the vertices of G can be partitioned into k sets S_i, such that whenever two vertices are in the same set S_i, they are adjacent.

Whether the cliquewidth of the graphs in this class is bounded by a constant k .
The cliquewidth of a graph is the number of different labels that is needed to construct the graph using the following operations:

creation of a vertex with label i,
disjoint union,
renaming labels i to label j,
connecting all vertices with label i to all vertices with label j.

Input:	A graph G in this class.
Output:	An expression that constructs G according to the rules for cliquewidth, using only a constant number of labels. Undefined if this class has unbounded cliquewidth.

Input:	A graph G in this class and an integer k.
Output:	True iff each vertex of G can be assigned one colour out of k such that whenever two vertices are adjacent, they have different colours.

Input:	A graph G in this class and an integer k.
Output:	True iff the cutwidth of G is at most k (see bounded cutwidth).

Input:	A graph G in this class and an integer k.
Output:	True iff G contains a set S of vertices, with \|S\| <= k, such that every vertex in G is either in S or adjacent to a vertex in S.

Input:	A graph G in this class and an integer k.
Output:	True iff G contains a set S of vertices, with \|S\| <= k, such that every cycle in G contains a vertex from S.

Input:	A graph G in this class.
Output:	True iff G has a simple cycle that goes through every vertex of the graph.

Input:	A graph G in this class.
Output:	True iff G has a simple path that goes through every vertex of the graph.

Input:	A graph G in this class and an integer k.
Output:	True iff G contains a set S of pairwise non-adjacent vertices, such that \|S\| >= k.

Input:	A graph G.
Output:	True iff G is in this graph class.

Input:	A graph G in this class and an integer k.
Output:	True iff the treewidth of G is at most k (see bounded treewidth).

Input:	A graph G in this class with weight function on the vertices and a real k.
Output:	True iff G contains a set S of pairwise adjacent vertices, such that the sum of the weights of the vertices in S is at least k.

Input:	A graph G in this class with weight function on the vertices and a real k.
Output:	True iff G contains a set S of vertices, such that the sum of the weights of the vertices in S is at most k and every cycle in G contains a vertex from S.

Input:	A graph G in this class with weight function on the vertices and a real k.
Output:	True iff G contains a set S of pairwise non-adjacent vertices, such that the sum of the weights of the vertices in S is at least k.

Graphclass: circular perfect

References

Complement classes

Inclusions

Map

Maximal subclasses

Problems