Arnaud Pêcher
email: arnaud.pecher@u-bordeaux.fr

Annegret K Wagler
email: annegret.wagler@uca.fr

On circular-perfect graphs: A survey

Keywords: circular-perfect graph, clique number, chromatic number

Circular-perfect graphs form a natural superclass of perfect graphs, introduced by Zhu almost 20 years ago: on the one hand due to their definition by means of a more general coloring concept, on the other hand as an important class of χ-bound graphs with the smallest non-trivial χ-binding function χ(G) ≤ ω(G) + 1.

In this paper, we survey the results about circular-perfect graphs obtained in the two last decades, with a focus on whether the fascinating properties of perfect graphs can be extended to this superclass. We recall the deep algorithmic properties of perfect graphs and the underlying polyhedral graph theory, in order to outline in this setting the main graph parameters that are also related to circular-perfect graphs. Finally, we give a list of open problems.

Introduction

Graph coloring theory has a central position in discrete mathematics -for its own interest as well as for the large variety of applications, dating back to the famous four-color problem stated by Guthrie in 1852 [START_REF] Guthrie | Tinting maps[END_REF].

In fact, partitioning a set of objects into classes according to certain rules is a fundamental process in discrete mathematics. The theory of graph coloring deals with this situation when the rule is to avoid conflicts between objects in the same class: one can create a conflict graph whose vertices correspond to the studied objects, and whose edges represent conflicts between pairs of objects. A coloring of the conflict graph then corresponds to a partition into conflict-free subsets (called color classes) or, equivalently, to an assignment of colors to the vertices such that adjacent vertices receive different colors.

More formally, let G = (V, E) be a graph with finite vertex set V and simple edge set E. A k-coloring of G is a mapping f : V → {1, . . . , k} with f (u) f (v) if uv ∈ E. That way, each color class is an independent set (or stable set) composed of pairwise non-adjacent vertices. The minimum k for which G admits a k-coloring is called the chromatic number of G and denoted by χ(G). Calculating χ(G) is an NP-hard problem in general [START_REF] Garey | Some simplified np-complete problems[END_REF].

The combinatorial concept being dual to colorings corresponds to cliques in a graph. In a set of k pairwise adjacent vertices, called clique K k , all k vertices have to be colored differently. Thus the size of a largest clique in G, the clique number ω(G), is a trivial lower bound on χ(G). This bound can be arbitrarily bad [START_REF] Mycielski | Sur le coloriage des graphes[END_REF] and is in general hard to evaluate as well [START_REF] Karp | Reducibility among Combinatorial Problems[END_REF].

It is often the case that certain combinatorial problems are easier to solve when the involved graphs G satisfy a max-min relation of the related graph parameters with equality. This is also the case here: Shannon observed in [START_REF] Shannon | The zero-error capacity of a noisy channel[END_REF] that the otherwise difficult problem of finding the zero-error capacity of a discrete memoryless channel becomes tractable for graphs G with ω(G) = χ(G).

This fact motivated Berge to study graphs G where ω(G ) = χ(G ) does not only hold for the graph G itself, but also for each induced subgraph G ⊆ G. Berge [START_REF] Berge | Färbung von Graphen deren sämtliche bzw. deren ungerade Kreise starr sind[END_REF] proposed to call a graph G perfect if each induced subgraph G ⊆ G admits an ω(G )-coloring.

Moreover, Berge observed that all chordless odd cycles C 2k+1 with k ≥ 2, called odd holes, and their complements, the odd antiholes C 2k+1 , satisfy ω(G) < χ(G). (The complement G of a graph G has the same vertex set as G and two vertices are adjacent in G if and only if they are non-adjacent in G.)

This motivated Berge's famous conjecture that a graph G is perfect if and only if G has no odd hole or odd antihole as induced subgraph. Many efforts to prove this conjecture stimulated the study of perfect graphs, revealing many fascinating structural properties of perfect graphs and interesting relationships to other fields of scientific enquiry. Most notably, the in general hard to compute parameters ω(G) and χ(G) can be determined in polynomial time if G is perfect by Grötschel, Lovász and Schrijver [START_REF] Grötschel | The ellipsoid method and its consequences in combinatorial optimization[END_REF]. The latter result relies on characterizations of perfect graphs in terms of different concepts, thereby establishing links to

• polyhedral theory (G is perfect if and only if certain polyhedra are identical);

• integer programming (a graph G is perfect if and only if certain linear programs have integral objective values);

• semidefinite programming (a graph is perfect if and only if the feasible region of a certain semidefinite program is a polytope); which indeed reflects the importance of perfect graphs in many different fields, see Section 2 for details.

As generalization of perfect graphs, Zhu [START_REF] Zhu | Circular-perfect graphs[END_REF] introduced the class of circular-perfect graphs based on a more general coloring concept introduced by Vince [START_REF] Vince | Star chromatic number[END_REF]. This variation of colorings is based on the observation that odd holes C 2k+1 satisfy ω(C 2k+1 ) = 2 and χ(C 2k+1 ) = 3, whereas their chromatic number should be intuitively about 2, as only one vertex needs to receive the third color. Vince aimed at refining the usual coloring concept taking this intuition into account. He defined the star chromatic number χ * (G) of a graph in such a way that indeed χ * (C 2k+1 ) = 2+ 1 k is satisfied for each odd hole, whereas χ * (K k ) = k still holds for every complete graph on k vertices.

Define a (k, d)-circular coloring of a graph G, as a mapping f :

V → {0, . . . , k -1} such that for each edge uv of G, d ≤ | f (u) -f (v)| ≤ k -d. The circular chromatic number is: χ c (G) = min k d : G has a (k, d)-circular coloring
From the definition, we immediately obtain χ c (G) ≤ χ(G) because a usual k-coloring of G is a (k, 1)-circular coloring.

Numerous works have been devoted to the circular-chromatic number and we refer to the two surveys by X. Zhu for a detailed overview [START_REF] Zhu | Circular chromatic number: a survey[END_REF][START_REF] Zhu | Recent developments in circular colouring of graphs[END_REF].

In view of the max-min relation between clique and chromatic number and to obtain a lower bound on χ c (G), Bondy and Hell [START_REF] Bondy | A note on the star chromatic number[END_REF] generalized cliques as follows. Let K k/d with k ≥ 2d denote the graph with the k vertices 0, . . . , k -1 and edges i j if and only if d ≤ |i-j| ≤ k -d. Such graphs K k/d are called circular cliques (note that they are also known as antiwebs in the literature, see [START_REF] Shepherd | Applying Lehman's theorem to packing problems[END_REF][START_REF] Wagler | Antiwebs are rank-perfect[END_REF]). A circular clique K k/d with gcd(k, d) = 1 is said to be prime. Prime circular cliques include all cliques K k = K k/1 as well as all odd antiholes C 2k+1 = K 2k+1/2 and all odd holes C 2k+1 = K 2k+1/k , see Figure 1.

Zhu [START_REF] Zhu | Circular-perfect graphs[END_REF] defined the circular clique number ω c (G) by

ω c (G) = max k d : K k/d ⊆ G, gcd(k, d) = 1
and we immediately obtain ω(G) ≤ ω c (G). Remark 1. Colorings can also be interpreted as homomorphisms from a graph to a clique. Let h be a homomorphism from

K 9/1 K 9/2 K 9/3 K 9/4
G 1 = (V 1 , E 1 ) to G 2 = (V 2 , E 2 ) where h : V 1 → V 2 such that h(u)h(v) ∈ E 2 if uv ∈ E 1 ; we write G 1 G 2 . Any k-coloring of a graph G is equivalent to a homomorphism from G to K k .
Then the circular chromatic number can be written as

χ c (G) = inf k d : G K k/d and the circular clique number as ω c (G) = sup k d : K k/d G, gcd(k, d) = 1 .
As both the infimum and the supremum are always attained, they can be replaced by minimum and maximum, respectively [START_REF] Zhu | Circular-perfect graphs[END_REF].

Every circular clique K k/d clearly admits a (k, d)-coloring (simply take the vertex numbers as colors, as in Figure 1) but no (k , d )-coloring with k d < k d by Bondy and Hell [START_REF] Bondy | A note on the star chromatic number[END_REF]. This implies that ω c (G) ≤ χ c (G) holds for any graph G, and we obtain the following chain of inequalities:

ω(G) ≤ ω c (G) ≤ χ c (G) ≤ χ(G). (1)
In analogy to perfect graphs, Zhu [START_REF] Zhu | Circular-perfect graphs[END_REF] called a graph G circular-perfect if, for each induced subgraph G ⊆ G, the circular clique number ω c (G ) and the circular chromatic number χ c (G ) coincide. Obviously, every perfect graph has this property by [START_REF] Bachoc | On the theta number of powers of cycle graphs[END_REF] as ω(G ) equals χ(G ). Moreover, it was proved by Zhu [START_REF] Zhu | Circular-perfect graphs[END_REF] that any circular clique is circular-perfect as well. Thus circular-perfect graphs constitute a proper superclass of perfect graphs (recall that odd holes and odd antiholes are examples of circular cliques).

A central question in the study of circular-perfect graphs is to look for parallels between the classes of perfect and circular-perfect graphs. Many results in this regard were obtained, already in the first years following their introduction (see [START_REF] Zhu | Circular-perfect graphs[END_REF] for a survey). The aim of this paper is to give a survey on the achievements that have been the outcome of the study of circular-perfect graphs during the two last decades.

The remaining of this paper is organized as follows:

• in Section 2, we give a brief overview of the nice algorithmic properties of perfect graphs and their roots coming from polyhedral graph theory and semi-definite programming;

• in Section 3, we outline the main graph parameters related to the circular-chromatic number and their linear programming formulations, which were introduced to refine perfectness concepts;

• in Section 4, we give an overview of the achieved results about circular-perfect graphs;

• in Section 5, we conclude this survey with some remarks and open problems.

About perfect graphs

Recall that Berge [START_REF] Berge | Färbung von Graphen deren sämtliche bzw. deren ungerade Kreise starr sind[END_REF] introduced perfect graphs, motivated from Shannon's problem of finding the zero-error capacity of a discrete memoryless channel [START_REF] Shannon | The zero-error capacity of a noisy channel[END_REF], as those graphs G satisfying

ω(G ) = χ(G ) for all induced subgraphs G ⊆ G. (2)
Berge further noticed that all examples of perfect graphs found also have the property that

α(G ) = χ(G ) for all induced subgraphs G ⊆ G, (3)
where α(G) denotes the stability number (the size of a largest stable set in G) and χ(G) the clique cover number (the least number of cliques covering V). Considering the complementary graph G where cliques of G turn into stable sets of G and, thus, colorings into clique covers, this means that every complement of a perfect graph G satisfies (3). This led Berge conjecture that a graph

G is perfect if and only if G is perfect. (4)
This conjecture was turned to the Perfect Graph Theorem by Lovász [START_REF] Lovász | Normal hypergraphs and the perfect graph conjecture[END_REF]. Moreover, recall that Berge observed that all odd holes C 2k+1 and odd antiholes C 2k+1 satisfy ω(G) < χ(G) which led Berge conjecture that a graph G is perfect if and only if G has no odd hole or odd antihole as induced subgraph.

(

) 5
This conjecture strongly stimulated the study of perfect graphs and was turned to the Strong Perfect Graph Theorem by Chudnovsky, Robertson, Seymour, and Thomas [START_REF] Chudnovsky | The strong perfect graph theorem[END_REF].

During the last decades, many fascinating structural properties of perfect graphs and interesting relationships to other fields of scientific enquiry have been discovered [START_REF] Golumbic | Algorithmic graph theory and perfect graphs[END_REF][START_REF]Perfect Graphs[END_REF][START_REF] Berge | Topics on Perfect Graphs[END_REF]. Most notably, the in general hard to compute parameters ω(G), χ(G), α(G) and χ(G) can be determined in polynomial time if G is perfect by Grötschel, Lovász and Schrijver [START_REF] Grötschel | The ellipsoid method and its consequences in combinatorial optimization[END_REF]. The latter result relies on characterizations of perfect graphs involving the stable set polytope. The stable set polytope STAB(G) of a graph G is defined as the convex hull of the incidence vectors of all stable sets of G. It can be alternatively represented by

STAB(G) = conv        x ∈ {0, 1} V : x(Q) = i∈Q x i ≤ 1, Q ⊆ G clique       
as a clique and a stable set have clearly at most one node in common and, thus, all clique constraints x(Q) ≤ 1 are valid for STAB(G). A canonical relaxation of STAB(G) is, therefore, the clique constraint stable set polytope

QSTAB(G) =        x ∈ R V : i∈Q x i ≤ 1, Q ⊆ G clique        .
We have STAB(G) ⊆ QSTAB(G) for all graphs, but equality for perfect graphs only [START_REF]On certain polytopes associated with graphs[END_REF][START_REF] Fulkerson | Anti-blocking polyhedra[END_REF][START_REF] Padberg | Perfect zero-one matrices[END_REF]:

G is perfect if and only if STAB(G) = QSTAB(G). (6)
Hence, one is tempted to look at the linear program max w T x, x ∈ QSTAB(G) for determining the weighted stability number α(G, w) for perfect graphs with a weight function w : V → R + .

The following chain of inequalities and equations is typical for integer/linear programming approaches to combinatorial problems:

α(G, w) = max{ i∈S w i : S ⊆ G stable} = max{w T x : x ∈ STAB(G)} = max{w T x : x(Q) ≤ 1 ∀cliques Q ⊆ G, x ≥ 0, x ∈ {0, 1} V } ≤ max{w T x : x(Q) ≤ 1 ∀cliques Q ⊆ G, x ≥ 0} = min{ Q y Q : Q i y Q ≥ w i ∀i ∈ G, y Q ≥ 0 ∀cliques Q ⊆ G} ≤ min{ Q y Q : Q i y Q ≥ w i ∀i ∈ G, y Q ≥ 0, y Q ∈ Z + ∀Q ⊆ G} = χ(G, w)
The inequalities come from dropping or adding integrality constraints, one of the equations is implied by linear programming duality. The last program can be interpreted as an integer programming formulation for determining the weighted clique cover number χ(G, w). It follows from the Perfect Graph Theorem that equality holds throughout the whole chain for all 0/1vectors w if and only if G is perfect. This, in turn, is equivalent to say that G is perfect if and only if the weighted fractional stability number

α f (G, w) = max w T x, x ∈ QSTAB(G) is integral ∀w ∈ {0, 1} V (7)
and results of Fulkerson [START_REF] Fulkerson | Blocking and antiblocking pairs of polyhedra[END_REF] and Lovász [START_REF] Lovász | A characterization of perfect graphs[END_REF] imply that this is true for all w ∈ Z V . Linear programming duality implies that this also applies to the weighted fractional clique cover number

χ f (G, w) = min        Q y Q : Q i y Q ≥ w i ∀i ∈ G, y Q ≥ 0 ∀cliques Q ⊆ G        .
However, solving the stable set problem for a perfect graph G by maximizing a linear objective function over QSTAB(G) does not work directly as it is shown in [START_REF] Grötschel | The ellipsoid method and its consequences in combinatorial optimization[END_REF] that optimizing over QSTAB(G) is NP-hard in general. Forall perfect graphs, it is possible via a detour involving a geometric representation of graphs from [START_REF] Lovász | On the shannon capacity of a graph[END_REF] and the corresponding semi-definite relaxation TH(G) of STAB(G) introduced in [START_REF] Grötschel | Geometric Algorithms and Combinatorial Optimization[END_REF].

For some N ∈ Z + , an orthonormal representation of a graph G is a sequence (u i : i ∈ V) of |V| unit-length vectors u i ∈ R N , such that u i T u j = 0 for all i j E. For any orthonormal representation of G and any additional unit-length vector c ∈ R N , the orthonormal representation constraint is i∈V (c T u i ) 2 x i ≤ 1. TH(G) denotes the convex set of all vectors x ∈ R V + satisfying all orthonormal representation constraints for G and is called the Theta-body.

As, on the one hand, every incidence vector of a stable set of G satisfies all orthonormal representation constraints and, on the other hand, every clique constraint is a special orthonormal representation constraint, we have for any graph G that

STAB(G) ⊆ TH(G) ⊆ QSTAB(G)
holds [START_REF] Grötschel | Geometric Algorithms and Combinatorial Optimization[END_REF] and that all three convex sets coincide by ( 6) if and only if G is perfect. More precisely, a beautiful characterization of perfect graphs is proved in [START_REF] Grötschel | Geometric Algorithms and Combinatorial Optimization[END_REF]:

G is perfect if and only if STAB(G) = TH(G) if and only if TH(G) = QSTAB(G). ( 8
)
The key property of TH(G) for linear programming was again established by Grötschel, Lovász, and Schrijver [START_REF] Grötschel | The ellipsoid method and its consequences in combinatorial optimization[END_REF]: approximating a linear objective function over TH(G) can be done with arbitrary precision in polynomial time. This deep result relies on the fact that the value

ϑ(G, w) = max w T x, x ∈ TH(G)
can be characterized in many equivalent ways, e.g., as the maximum eigenvalue of a certain set of symmetric matrices, as the value of some function involving orthonormal representations, or as the value of a semidefinite program, see [START_REF] Grötschel | Geometric Algorithms and Combinatorial Optimization[END_REF] for details. As we have α(G, w) = ϑ(G, w) for all perfect graphs G by [START_REF] Coulonges | Triangle-free strongly circular-perfect graphs[END_REF], this finally implies that the weighted stable set problem can be solved in polynomial time for perfect graphs. Therefore, the weighted clique cover number χ(G, w) = α(G, w), the weighted chromatic number χ(G, w) = χ(G, w), and the weighted clique number ω(G, w) = χ(G, w) = α(G, w) can also be computed in polynomial time for perfect graphs G, by calculating ϑ(G, w) or ϑ(G, w), which clearly applies to the unweighted versions by setting w = 1 = (1, . . . , 1).

Graph parameters related to the circular chromatic number

In this section, we study different graph parameters related to the circular chromatic number. We first address the case of unweighted graphs, then we address the more general situation of weighted graphs which allows us to define a weighted version of circular-perfection. For that, we study chains of inequalities of the considered graph parameters and ask for the particular situation when equality holds between certain pairs of graph parameters.

Unweighted graphs. Recall the inequality chain (1) for the usual and the circular clique and chromatic numbers giving rise to the definition of circular-perfect graphs.

We can integrate the fractional clique number ω f (G) = α f (G, 1) and the fractional chromatic number χ f (G) = χ f (G, 1) into this inequality chain as follows [START_REF] Pêcher | Polynomial time computability of some graph parameters for superclasses of perfect graphs[END_REF]:

ω(G) ≤ ω c (G) ≤ ω f (G) = χ f (G) ≤ χ c (G) ≤ χ(G).
In addition, Zhu [START_REF] Zhu | Circular-perfect graphs[END_REF] showed that ω(G) = ω c (G) and Vince [START_REF] Vince | Star chromatic number[END_REF] noticed that χ c (G) = χ(G) holds for all graphs. Hence, we can refine the above chain of inequalities for the unweighted case as follows:

Corollary 2. For every graph G, we have that

ω(G) = ω c (G) ≤ ω c (G) ≤ ω f (G) = χ f (G) ≤ χ c (G) ≤ χ c (G) = χ(G).
Recall that for perfect graphs G, we have equality throughout the whole chain of inequalities, whereas equality of ω c (G) and χ c (G) is required for circular-perfect graphs. Further implications are discussed in Section 4.

Weighted graphs. Let G = (V, E) be a graph with weight function w : V → R + . Whenever a graph parameter p(G) can be obtained by optimizing a linear objective function over a certain polyhedron P(G) associated with G, then the weighted version of p(G) corresponds to p(G, w) = max / min w T x, x ∈ P(G) . This is the case for the weighted versions of the different studied clique numbers. The clique polytope CLI(G) of a graph G is the stable set polytope of its complement G, and the fractional clique polytope CLI f (G) is the fractional stable set polytope of G. Hence,

CLI(G) = STAB(G) ⊆ QSTAB(G) = CLI f (G) (9)
implies that

ω(G, w) = max w T x : x ∈ CLI(G) ≤ max w T x : x ∈ CLI f (G) = ω f (G, w)
where ω f (G, w) is the weighted fractional clique number.

In order to find a suitable polytope such that optimizing over this polytope yields the (weighted) circular-clique number ω c (G, w), Pêcher and Wagler [START_REF] Pêcher | Polynomial time computability of some graph parameters for superclasses of perfect graphs[END_REF] introduced the circular-clique polytope

CLI c (G) = conv 1/α(K)x K : K ⊆ G prime circular-clique where x K denotes the incidence vector of K ⊆ G, i.e., x K v = 1 if v ∈ K and x K v = 0 otherwise. By ω c (G, w) = max        1 α(K)        v∈K w(v)        : K ⊆ G prime circular-clique        we immediately see that ω c (G, w) = max w T x : x ∈ CLI c (G) holds.
In [START_REF] Pêcher | Polynomial time computability of some graph parameters for superclasses of perfect graphs[END_REF] it is further shown that CLI c (G) is sandwiched between the clique polytope and the fractional clique polytope: Theorem 3 ( [START_REF] Pêcher | Polynomial time computability of some graph parameters for superclasses of perfect graphs[END_REF]). For all graphs G, we have

CLI(G) ⊆ CLI c (G) ⊆ CLI f (G) and thus ω(G, w) ≤ ω c (G, w) ≤ ω f (G, w)
follows for all possible weights w.

A graph is called a-perfect if its stable set polytope is described by 0/1-valued contraints associated with prime circular cliques only [START_REF] Wagler | On rank-perfect subclasses of near-bipartite graphs[END_REF]. Pêcher and Wagler [START_REF] Pêcher | Computing the clique number of a-perfect graphs in polynomial time[END_REF] showed:

Theorem 4 ([32]). CLI c (G) = CLI f (G) holds if and only if G is a-perfect.
As equality of two polyhedra immediately implies that the corresponding graph parameters are equal for all possible weights w, we obtain: Corollary 5 ( [START_REF] Pêcher | Computing the clique number of a-perfect graphs in polynomial time[END_REF]). We have ω c (G, w) = ω f (G, w) for all weights w if and only if G is a-perfect.

Recall that TH(G) is sandwiched between STAB(G) and QSTAB(G). This translates to

CLI(G) ⊆ TH(G) ⊆ CLI f (G) and further implies ω(G, w) ≤ ϑ(G, w) ≤ ω f (G, w).
Hence, both parameters ω c (G, w) and ϑ(G, w) are sandwiched between ω(G, w) and ω f (G, w), but are incomparable in general. For instance, consider the 5-hole C 5 = K 5/2 and the 5-wheel W 5 = K 5/2 * K 1 obtained from a 5-hole by adding a further vertex completely joined to all vertices of the C 5 , then we have

√ 5 = ϑ(C 5 , 1) < ω c (C 5 , 1) = 5 2 but 3 = ω c (W 5 , 1) < ϑ(W 5 , 1) = √ 5 + 1,
hence incomparability holds even in the unweighted case with 1 = (1, . . . , 1).

Deuber and Zhu [START_REF] Deuber | Circular coloring of weighted graphs[END_REF] introduced circular colorings of weighted graphs as follows. Let G = (V, E) be a graph with weight function w : V → R + and C be a circle of lenght t in the plane. A t-circular coloring of (G, w) is a mapping A which assigns to every vertex v ∈ V an open arc A(v) on C such that the lenght of A(v) is at least w(v) and A(v) is disjoint from A(u) whenever uv ∈ E. The weighted circular chromatic number of (G, w) is

χ c (G, w) = min{t : (G, w) has a t-circular coloring}.
Furthermore, a t-interval coloring of (G, w) is obtained when the arcs A(v) are placed within an interval of lenght t and χ I (G, w) = min{t : (G, w) has a t-interval coloring} is the interval chromatic number of (G, w). Deuber and Zhu [START_REF] Deuber | Circular coloring of weighted graphs[END_REF] showed: Theorem 6 ( [START_REF] Deuber | Circular coloring of weighted graphs[END_REF]). For all graphs G and for all weights w, we have

ω(G, w) ≤ ω f (G, w) = χ f (G, w) ≤ χ c (G, w) ≤ χ I (G, w).
Graphs with ω(G, w) = χ I (G, w) for all possible weights w are known as superperfect, see e.g. Golumbic [START_REF] Golumbic | Algorithmic graph theory and perfect graphs[END_REF]. In analogy, Deuber and Zhu called a graph G star-superperfect if ω f (G, w) = χ c (G, w) holds for all possible weights w.

By definition, superperfect graphs are star-superperfect. In addition, it was shown in [START_REF] Deuber | Circular coloring of weighted graphs[END_REF]:

Theorem 7 ([9]
). All odd holes and odd antiholes are star-superperfect.

Hence, star-superperfect graphs form a proper superclass of superperfect graphs as odd holes and odd antiholes are obviously not superperfect.

Moreover, combining the chains from Theorem 3, Theorem 6 and linear programming duality finally provides us the following: Corollary 8. For all graphs G and for all weights w, we have

ω(G, w) ≤ ω c (G, w) ≤ ω f (G, w) = χ f (G, w) ≤ χ c (G, w) ≤ χ I (G, w).
Taking both concepts, a-perfection and star-superperfection together allows us to define circular-superperfect graphs as precisely those graphs G that are a-perfect and star-superperfect such that

ω c (G, w) = ω f (G, w) = χ f (G, w) = χ c (G, w)
holds for all possible weights w. From Corollary 8 it is clear that every superperfect graph is circular-superperfect . By [START_REF] Wagler | Antiwebs are rank-perfect[END_REF], all circular cliques (and thus particularly all odd holes and odd antiholes) are aperfect. Combining this result with Theorem 7, we conclude: Corollary 9. Odd holes and odd antiholes are circular-superperfect graphs.

An affirmative answer to the question from [START_REF] Deuber | Circular coloring of weighted graphs[END_REF] whether all circular cliques are star-superperfect would imply that all circular cliques are circular-superperfect graphs.

Furthermore, also in [START_REF] Deuber | Circular coloring of weighted graphs[END_REF], Deuber and Zhu called a graph G star-perfect if ω f (G, w) = χ c (G, w) holds for all 0/1-valued weights w. By definition, it is clear that all superperfect graphs, all circular-superperfect graphs, and all star-superperfect graphs are star-perfect.

As χ I (G, w) corresponds to the chromatic number of some subgraph of G for all 0/1-valued weights w, we have for perfect graphs that equality holds through the whole chain from Corollary 8 for all such weights and, thus, every perfect graph is star-perfect.

Moreover, as the condition required for star-perfection can be translated to the unweighted versions of the parameters ω f (G ) and χ c (G ) for induced subgraphs G' of G by [START_REF] Zhu | Star chromatic numbers and products of graphs[END_REF], all circularperfect graphs are star-perfect.

About circular-perfect graphs

A natural extension of perfect graphs was introduced by Gyárfás [ Considering the inequality chain from Corollary 2 for circular-perfect graphs G yields

ω(G) = ω c (G) ≤ ω c (G) = ω f (G) = χ f (G) = χ c (G) ≤ χ c (G) = χ(G)
which implies that circular-perfect graphs G satisfy the following Vizing-like property

ω(G) ≤ χ(G) ≤ ω(G) + 1. (10)
Thus, circular-perfect graphs are a class of χ-bound graphs with the smallest non-trivial χbinding function. In particular, this χ-binding function is best possible for a proper superclass of perfect graphs implying that circular-perfect graphs admit coloring properties almost as nice as perfect graphs.

In this section, we give an overview of the achieved results about circular-perfect graphs and whether the fascinating properties of perfect graphs can be extended to this superclass.

Families of circular-perfect graphs

By definition, circular-perfect graphs do include all perfect graphs, and therefore every of their famous subclasses, such as bipartite graphs, line graphs of bipartite graphs, chordal graphs, comparability graphs, perfectly orderable graphs . . . As of circular-perfect graphs, several "natural" families of circular-perfect graphs have also been exhibited, that we describe in the following.

Planar circular-perfect graphs have been investigated: though it is easy to build many planar graphs that are circular-imperfect [START_REF] Pêcher | On classes of minimal circular-imperfect graphs[END_REF][START_REF] Pêcher | Three classes of minimal circular imperfect graphs[END_REF][START_REF] Xu | Some results on circular-perfect graphs and perfect graphs[END_REF], every outerplanar graph is circular-perfect [START_REF] Pêcher | On classes of minimal circular-imperfect graphs[END_REF].

A convex-round graph is a graph whose vertices can be circularly enumerated so that the neighborhood of each vertex forms an interval in the enumeration. Bang-Jensen and Huang proved that every convex-round graph is circular-perfect [START_REF] Bang-Jensen | Convex-round graphs are circular-perfect[END_REF], thereby extending Zhu's result that circular-cliques are circular-perfect [START_REF] Zhu | Circular-perfect graphs[END_REF].

In contrary to perfect graphs, the class of circular-perfect graphs is not stable under complementation. A circular-perfect graph is strongly circular-perfect if its complement is circularperfect as well. This subclass entails perfect graphs, odd holes, and odd antiholes. Bang-Jensen and Huang asked to determine strongly circular-perfect graphs [START_REF] Bang-Jensen | Convex-round graphs are circular-perfect[END_REF]. Coulonges et al. established a characterization of triangle-free ones: a graph G is triangle-free strongly circular-perfect if and only if G is bipartite or a so-called interlaced odd hole [START_REF] Coulonges | Triangle-free strongly circular-perfect graphs[END_REF] (see Figure 4.1 for an example of a interlaced odd hole). Further subclasses of circular-perfect graphs can be defined by restricting the set of prime circular cliques that may occur. For instance, in [START_REF] Pêcher | Computing clique and chromatic number of circular-perfect graphs in polynomial time[END_REF] a circular-perfect graph is called basic if its only prime circular cliques are cliques, odd antiholes and odd holes. Results from [START_REF] Coulonges | Triangle-free strongly circular-perfect graphs[END_REF][START_REF] Pêcher | Computing clique and chromatic number of circular-perfect graphs in polynomial time[END_REF][START_REF] Pêcher | Claw-free circular-perfect graphs[END_REF] show that strongly circular-perfect graphs, planar circular-perfect graphs, and claw-free circularperfect graphs are all basic.

Some necessary and sufficient conditions

Recall that a graph is perfect if and only if every induced subgraph H has an independent set S such that ω(H -S ) < ω(H). Xu proved a similar statement for circular-perfect graphs: every induced subgraph H of a circular-perfect graph has an independent set S such that ω c (H -S ) < ω c (H) [START_REF] Xu | Some results on circular-perfect graphs and perfect graphs[END_REF]; however the converse may not be true.

A graph G such that the closed neighborhood N[v] of every vertex v induces a perfect graph G v is called neighborhood-perfect graphs in [START_REF] Pêcher | Facets of Combinatorial Optimization[END_REF]. Zhu proved that every circular-perfect graph is neighborhood-perfect, and conversly that every neighborhood-perfect graph G such that for each vertex x of G, G -N G [x] induces a bipartite graph which contains no induced P 5 , is circularperfect [START_REF] Zhu | Perfect graphs for generalized colouring-circular-perfect graphs[END_REF][START_REF] Zhu | Circular-perfect graphs[END_REF].

Circular-perfect graphs that are complete joins have a straightforward characterization [START_REF] Pêcher | On classes of minimal circular-imperfect graphs[END_REF][START_REF] Pêcher | Three classes of minimal circular imperfect graphs[END_REF][START_REF] Xu | On minimally circular-imperfect graphs[END_REF]: the complete join G * G of two graphs G and G is circular-perfect if and only if both G and G are perfect.

As shown by Xu in [START_REF] Xu | On minimally circular-imperfect graphs[END_REF], the line graph L(G) of a cubic graph G is circular-perfect if and only if G is 3-edge colorable. Hence a characterization of claw-free circular-perfect graphs would imply a characterization of critically non-3-edge colorable cubic graphs, which is known to be a difficult problem. Pêcher and Zhu [START_REF] Pêcher | Claw-free circular-perfect graphs[END_REF] proved that connected claw-free circular-perfect graphs G with χ(G) > ω(G) satisfy min{α(G), ω(G)} = 2

Forbidden induced subgraphs: minimal circular-imperfect graphs

As analogue to the Strong Perfect Graph Theorem, one might be tempted to ask for an appealing conjecture on minimal forbidden subgraphs in circular-perfect graphs. A graph G is minimal circular-imperfect if G is not circular-perfect but every proper induced subgraph is.

A consequence of the strong perfect graph theorem is that minimal imperfect graphs G have min{α(G), ω(G)} = 2. In contrast to this result, it is shown in [START_REF] Pan | Minimal circular-imperfect graphs of large clique number and large independence number[END_REF] that minimal circular-imperfect graphs G can have arbitrarily large independence number and arbitrarily large clique number: for each even integer k, there is a minimal circular-imperfect graph G with min(α(G), ω(G)) = k. They also introduce another infinite family of minimal circular-imperfect graphs G with min(α(G), ω(G)) = 4 and another one satisfying min{α(G), ω(G)} = 2. However claw-free minimal circular-imperfect graphs can not have stable sets and cliques both of size at least 4 [START_REF] Pêcher | Claw-free circular-perfect graphs[END_REF].

Several families of planar minimal circular-imperfect graphs have been exhibited: so-called odd hole necklaces [START_REF] Pêcher | On classes of minimal circular-imperfect graphs[END_REF][START_REF] Pêcher | Three classes of minimal circular imperfect graphs[END_REF] depicted in Figure 4.3, graphs obtained by identifying one common edge in two odd holes of same size and adding one extra edge [START_REF] Xu | Some results on circular-perfect graphs and perfect graphs[END_REF].

Odd wheels and odd antiwheels are two basic families of minimally circular-imperfect graphs [START_REF] Pêcher | Three classes of minimal circular imperfect graphs[END_REF][START_REF] Xu | On minimally circular-imperfect graphs[END_REF]. Kupfahl et al. described several different families of minimally circular-imperfect triangle-free graphs [START_REF] Kuhpfahl | Circular-imperfection of triangle free graphs[END_REF]. In [START_REF] Coulonges | Triangle-free strongly circular-perfect graphs[END_REF], strongly ones are fully characterized: a graphs is a minimal triangle-free strongly-circular imperfect graph if and only if it is an odd antiwheel or a so called extended odd hole.

In 1974, Padberg proved that minimal imperfect graphs are partitionable [START_REF] Padberg | Perfect zero-one matrices[END_REF]: given two integers p and q greater or equal than 2, a graph G is called (p, q)-partitionable if |V(G)| = pq + 1 and, for each vertex v of G, the subgraph G \ {v} admits a partition into p cliques of cardinality q as well as a partition into q stable sets of cardinality p. As minimal-imperfect graphs are Figure 3: Example of an odd hole necklace circular-perfect due to the Strong Perfect Graph Theorem, one may expect that most of them are circular-perfect. It turns out that this is the opposite: all partitionable graphs apart from circular cliques are circular-imperfect [START_REF] Pêcher | On classes of minimal circular-imperfect graphs[END_REF][START_REF] Pêcher | Three classes of minimal circular imperfect graphs[END_REF]. This implies that partitionable graphs are likely to contain many minimal circular-imperfect graphs. Given a graph G, an edge e of G is called indifferent if e is not contained in any maximum clique of G. The normalized subgraph norm(G) of G is obtained from G by deleting all indifferent edges. The normalized subgraph of a partitionable graph is still partitionable. Any circular clique K n/q (and its complement) with n = 1 (mod q) is a partitionable graph. It follows that, if K p/q is any prime circular clique, then norm(K p/q ) is 1. circular-imperfect if and only if p -1 (mod q) and p/q ≥ 3; 2. minimal circular-imperfect if and only if p = 3q + 1 and q ≥ 3 [START_REF] Pêcher | On classes of minimal circular-imperfect graphs[END_REF][START_REF] Pêcher | Three classes of minimal circular imperfect graphs[END_REF].

Xu gave a characterization of minimal circular-imperfect graphs that are line graphs. A graph is called k-critical if k = ∆(G), its chromatic index χ (G) is k + 1 and for every edge e, χ (Ge) < χ (G). Xu established [START_REF] Xu | Some results on circular-perfect graphs and perfect graphs[END_REF] that a line graph L(H) is minimal circular-imperfect if and only if H is a 3-critical graph.

Using a construction method to build series-parallel graphs with given circular-chromatic number from [START_REF] Pan | Density of the circular chromatic numbers of series-parallel graphs[END_REF], Zhu provided an infinite family of minimal circular-imperfect graphs that are series-parallel: Theorem 10 ( [START_REF] Zhu | Circular-perfect graphs[END_REF]). If k/d is a rational number and there is an integer q ≥ 2 such that (2q+1)d = kq -1, then there is a minimal circular imperfect series-parallel graph G with χ c (G) = k/d. Therefore, many different families of minimal circular-imperfect graph have been discovered and they do not appear to have a straightforward common structure, hence formulating an analogue to the Strong Perfect Graph Theorem for circular-perfect graphs seems very unlikely.

Algorithmic results about circular-perfect graphs

The complexity of recognizing circular-perfect graphs is still open, though both the recognition problem and the weighted independence number can be solved in polynomial time for triangle-free strongly circular-perfect graphs [START_REF] Coulonges | Triangle-free strongly circular-perfect graphs[END_REF].

As computing clique and chromatic number in polynomial time is one of the key milestone of perfect graph theory, several authors studied whether this result could be extended to the graph parameters relevant for circular-perfect graphs.

A first step in this direction was obtained in [START_REF] Pêcher | Polynomial time computability of some graph parameters for superclasses of perfect graphs[END_REF] whose authors showed that, for any neighborhoodperfect graph G, the strong optimization problem over QSTAB(G) can be solved in polynomial time. For neighborhood-perfect graphs G, α f (G, w) can thus clearly be calculated in polynomial time, but also the weighted clique number by

ω(G, w) = max{ϑ(G v , w) : v ∈ V(G)}.
As circular-perfect graphs are neighborhood-perfect, this implies: Corollary 11 ( [START_REF] Pêcher | Polynomial time computability of some graph parameters for superclasses of perfect graphs[END_REF]). If G is circular-perfect, then ω(G, w) and ω f (G, w) = χ f (G, w) are computable in polynomial time for any weight vector w.

We further can conclude for the unweighted versions of the studied graph parameters:

Corollary 12 ([29]). If G is strongly circular-perfect, then ω(G), ω c (G) = ω f (G) = χ f (G) = χ c (G)
, and χ(G) can be computed in polynomial time.

As strongly circular-perfect graphs are closed under complementation, we can also compute their (weighted) stability number α(G, w) = ω(G, w) in polynomial time, which generalizes a result of [START_REF] Coulonges | Triangle-free strongly circular-perfect graphs[END_REF] for triangle-free strongly circular-perfect graphs.

In [START_REF] Pêcher | Computing clique and chromatic number of circular-perfect graphs in polynomial time[END_REF], the authors asked further whether it is possible to obtain the unweighted clique number of circular-perfect graphs by a single evaluation of ϑ(G) and whether the Vizing bound [START_REF] Fulkerson | Blocking and antiblocking pairs of polyhedra[END_REF] can be used to compute the chromatic number of a circular-perfect graph in polynomial time, as we have for such graphs that ω

(G) ≤ ϑ(G) ≤ χ(G) ≤ ω(G) + 1 holds. Hence ω(G) = ϑ(G) and χ(G) = ϑ(G) follows for ϑ(G) Z. Combining the facts ω(G) ≤ ϑ(G) ≤ ω c (G) = ω f (G) and ω(G) = ω c (G) ,
it was shown: Corollary 13 ( [START_REF] Pêcher | Computing clique and chromatic number of circular-perfect graphs in polynomial time[END_REF]). If G is circular-perfect, then ω(G) = ϑ(G) holds and is computable in polynomial time.

Moreover, it is possible to calculate χ(G) by rounding up the value ϑ(G), provided that the case ω(G) = ϑ(G) < χ(G) can be excluded. For that, based on the well-known fact that if G is homomorphic to H then ϑ(G) ≤ ϑ(H), the following key property of circular-perfect graphs has been established: if G is circular-perfect and χ c (G) = p/q, then ϑ(G) = ϑ(K p/q ) holds.

As a consequence, the following result was obtained:

Theorem 14 ( [START_REF] Pêcher | Computing clique and chromatic number of circular-perfect graphs in polynomial time[END_REF]). If G is circular-perfect then χ(G) = ϑ(G) holds and is computable in polynomial time.

In [START_REF] Pêcher | Computing clique and chromatic number of circular-perfect graphs in polynomial time[END_REF], the authors asked further whether the polynomial time computability even extends to circular clique and circular chromatic number, making use of the above mentioned key property of circular-perfect graphs, which implies that χ c (G) = p/q can be calculated, provided that it is possible to compare the value ϑ(G) with ϑ(K p/q ) for all prime induced circular cliques K p/q ⊆ G, though ω c (G) and χ c (G) are not integers, and neither ϑ(G) is sandwiched between the two parameters.

As first step, it was shown in [START_REF] Pêcher | Computing clique and chromatic number of circular-perfect graphs in polynomial time[END_REF] that this is possible for all basic circular-perfect graphs as only a restricted set of prime circular cliques can occur by definition (namely cliques, odd antiholes and odd holes). As a consequence, circular clique and circular chromatic number can be computed in polynomial time for claw-free circular-perfect graphs and planar circular-perfect graphs as they are subclasses of basic circular-perfect graphs by [START_REF] Pêcher | Claw-free circular-perfect graphs[END_REF] and [START_REF] Pêcher | Computing clique and chromatic number of circular-perfect graphs in polynomial time[END_REF], resp.

To ensure the polynomial time computability of χ c (G) for all circular-perfect graphs, it is sufficient to prove that the values ϑ(K k/d ) with k, d ≤ n are all distinct and separated by at least ε for some ε with polynomial space encoding.

Bachoc et al. [START_REF] Bachoc | On the theta number of powers of cycle graphs[END_REF] determined a closed formula for the theta values of circular cliques, which allowed them to prove that the circular chromatic numbers of circular-cliques are indeed distinct. As a consequence, they could prove: Theorem 15 ( [START_REF] Bachoc | On the theta number of powers of cycle graphs[END_REF]). For every circular-perfect graph, the circular-chromatic number is computable in polynomial time.

Furthermore, the Lovász number of the complement of a circular-perfect graph is asymptoticaly close to its circular chromatic number.

ϑ(G) = k d + O 1 k .
This nicely extends the algorithmic results for perfect graphs to the larger class of circularperfect graphs, but does not give any polynomial time combinatorial algorithm relying on the structure of circular-perfect graphs. Such algorithms have been provided for several classes of circular-perfect graphs, including convex-round graphs [START_REF] Bang-Jensen | Convex-round graphs are circular-perfect[END_REF], triangle-free strongly circular-perfect graphs [START_REF] Coulonges | Triangle-free strongly circular-perfect graphs[END_REF] and claw-free circular-perfect graphs [START_REF] Pêcher | Claw-free circular-perfect graphs[END_REF].

Summary

Putting it all together, we get the following picture of the current landscape of circular-perfect graphs:

perfect

Concluding remarks and open problems

The study of circular-perfect graphs motivated by Zhu's work has revealed many interesting results so that we can conclude that circular-perfect graphs indeed generalize perfect graphs in several respects, notably concerning coloring and algorithmic properties.

Nevertheless, some interesting questions regarding circular-perfect graphs remain open and are listed in Section 5.1.

On the other hand, the strong properties of circular-perfect graphs motivate in turn to ask whether several of them remain true for other graph classes related to circular-perfect graphs or for some superclasses generalizing circular-perfect graphs. These issues are finally addressed in Section 5.2 for weighted versions of circular-perfection and in Section 5.3 for algorithmic properties of superclasses.

Open problems on circular-perfect graphs

The many interesting properties of circular-perfect graphs motivate of course the question to find as many examples of circular-perfect graphs as possible -as all of them benefit from these properties. Towards this goal, it is clearly helpful to exhibit more properties of circular-perfect graphs, in particular: Problem 17. Identify more necessary and/or sufficient conditions for circular-perfection.

This would be helpful to solve the following problem: Problem 18. Identify further subclasses of circular-perfect graphs.

Recall from Section 4 that, in contrary to perfect graphs, the class of circular-perfect graphs is not closed under complementation, but that strongly circular-perfect graphs build the complementary core of circular-perfect graphs. As strongly circular-perfect graphs have not yet been characterized, two natural questions arise in this context: Problem 19 ( [START_REF] Bang-Jensen | Convex-round graphs are circular-perfect[END_REF]). Determine the strongly circular-perfect graphs.

Problem 20 ([8]). Find (the) minimal not strongly circular-perfect graphs.

Recall from Section 4.3 further that many different families of minimal circular-imperfect graphs have been discovered, but lack a common structure so that it seems to be difficult to even formulate an analogue to the Strong Perfect Graph Theorem for circular-perfect graphs. However, several authors asked to characterize the minimal circular-imperfect graphs within a certain graph class, as e.g. already done for partitionable graphs [START_REF] Pêcher | On classes of minimal circular-imperfect graphs[END_REF][START_REF] Pêcher | Three classes of minimal circular imperfect graphs[END_REF] and line graphs [START_REF] Xu | Some results on circular-perfect graphs and perfect graphs[END_REF].

Problem 21 ([19]). Find (the) minimal circular-imperfect graphs that are triangle-free. Problem 22 ([28]). Find (the) minimal circular-imperfect graphs that are planar. Problem 23 ([33]). Find (the) minimal circular-imperfect graphs that are claw-free.

Moreover, it seems difficult to find a characterization of circular-perfect graphs that allows to recognize them in polynomial time.

Weighted versions of circular-perfection

Recall from Section 3 that Deuber and Zhu [START_REF] Deuber | Circular coloring of weighted graphs[END_REF] showed that

ω(G, w) ≤ ω f (G, w) = χ f (G, w) ≤ χ c (G, w) ≤ χ I (G, w)
holds for all graphs G and for all weights w, and that a graph is called star-superperfect if ω f (G, w) = χ c (G, w) holds for all possible weights w. Deuber and Zhu [START_REF] Deuber | Circular coloring of weighted graphs[END_REF] noticed that superperfect graphs are star-superperfect (as they satisfy ω(G, w) = χ I (G, w) for all w) and showed that odd holes and odd antiholes are further examples of star-superperfect (Theorem 7). As circular cliques are generalizations of both odd holes and odd antiholes, they asked the following natural question: Problem 24 ( [START_REF] Deuber | Circular coloring of weighted graphs[END_REF]). Are all circular cliques star-superperfect graphs?

In addition, Deuber and Zhu [START_REF] Deuber | Circular coloring of weighted graphs[END_REF] formulated the following problems: Problem 25 ( [START_REF] Deuber | Circular coloring of weighted graphs[END_REF]). Is it true that χ c (G, w) = χ I (G, w) for every w if and only if G is superperfect? Problem 26 ([9]). Is it true that χ c (G, w) = χ I (G, w) for every 0/1-valued w if and only if G is perfect? Problem 27 ([9]). Is it possible to determine χ c (G, w) in polynomial time for G star-superperfect? Moreover, we know that all perfect graphs G satisfy ω(G, w) = χ(G, w) for all integral weights w, where χ(G, w) denotes the weighted chromatic number, that is the minimum number of stable sets needed to cover each vertex v of G with at least w(v) of them. It is known that

χ(G, w) ≤ χ I (G, w)
holds for all graphs G and for all w, as every interval coloring is a weighted coloring satisfying the additional property that the w(v) colors assigned to each vertex v are consecutive.

In view of the fact that the circular chromatic number is a lower bound of the chromatic number for any unweighted graph, it is natural to expect the same relation for the weighted case. However, the Petersen graph P with weights w = (2, . . . , 2) provides a counterexample. The unique minimum weighted coloring of (P, w) is shown in Figure 5.2. It uses all 5 maximum stable sets of P which all together cover each vertex of P exactly twice. However, only the colors assigned to the vertices in the inner 5-cycle satisfy the condition of the weighted circular coloring, hence χ(P, w) < χ c (P, w)

follows for the chosen weights w = (2, . . . , 2). This shows that, in contrary to the unweighted case, the weighted circular chromatic number based on t-circular colorings is not always a lower bound of the weighted chromatic number for any weighted graph.

However, we do not yet know any perfect graph G with χ(G, w) < χ c (G, w) for some weight w. This motivates the following question:

Problem 28. Is it true that χ c (G, w) ≤ χ(G, w) ≤ χ I (G, w)
holds for all perfect graphs G and all (integral) weights w?

If yes, this would also give an affirmative answer to the following question:

Problem 29. Are all perfect graphs star-superperfect?

Moreover, recall from Section 3 that a circular-superperfect graph G is both a-perfect (such that ω c (G, w) = ω f (G, w) holds for all w) and star-superperfect (such that χ f (G, w) = χ c (G, w) holds for all w).

Recall further that equality of two graph parameters for certain graphs and all possible weights is often due to equality of the associated polyhedra. This is the case for a-perfect graphs G by [START_REF] Pêcher | Computing the clique number of a-perfect graphs in polynomial time[END_REF] as the circular-clique polytope CLI c (G) (needed to compute ω c (G, w)) coincides with the fractional clique polytope CLI f (G) (needed to compute ω f (G, w)) if and only if G is a-perfect. This implies that the two maxima are equal, regardless which objective function w T x is maximized over CLI c (G) = CLI f (G). Moreover, by linear programming duality, χ f (G, w) can be computed by minimizing over the polyhedron COL f (G) defined by the dual constraint system of CLI f (G), see e.g. Deuber and Zhu [START_REF] Deuber | Circular coloring of weighted graphs[END_REF].

This motivates the following natural questions: An affirmative answer to these two questions would further imply that circular-superperfect graphs are correlated to the equality of two pairs of polyhedra where linear programming duality ensures that the optimal values from both pairs (the maximum over CLI c (G) = CLI f (G) and the minimum over COL f (G) = COL c (G)) are the same.

Algorithmic results beyond circular-perfection

We have seen in Section 4.4 that circular-perfect graphs share the nice algorithmic properties with perfect graphs, even using similar techniques involving the theta-function.

However, as mentioned in Section 4.5, it is still open whether the stability number of a circular-perfect graph can be found in polynomial time. Recall that the strong optimization problem over QSTAB(G) can be solved in polynomial time for all members of a superclass of circular-perfect graphs, namely the neighborhood-perfect graphs (where the closed neighborhood of every vertex induces a perfect graph), which implies that the fractional stability number α f (G, w) can be calculated in polynomial time.

In view of the results from Section 4.4, one is tempted to ask for the unweighted version:

Problem 32. Is it true that, for a circular-perfect graph G, α(G) = α f (G) holds and, thus, can be calculated in polynomial time?

In addition, the class of all graphs satisfying the Vizing-like property [START_REF] Fulkerson | Blocking and antiblocking pairs of polyhedra[END_REF] for the chromatic number constitutes a further superclass of circular-perfect graphs, say Vizing-bound graphs. It is a natural question to ask whether the approach to determine ω(G) and χ(G) by rounding the value ϑ(G) can be applied to further Vizing-bound graphs. However, in [START_REF] Pêcher | Computing clique and chromatic number of circular-perfect graphs in polynomial time[END_REF][START_REF] Pêcher | Facets of Combinatorial Optimization[END_REF] it was noticed that this is not possible for two prominent classes of Vizing-bound graphs, namely line graphs and planar graphs (notice that line graphs even belong to the intersection of neighborhood-perfect and Vizing-bound graphs). This motivates the following question: Problem 33. Find classes of neighborhood-perfect and Vizing-bound graphs G such that ω(G) = ϑ(G) and χ(G) = ϑ(G) holds.

Finally, recall that all algorithmic results for circular-perfect graphs rely on the evaluation of the theta-function, but not on the structure of circular-perfect graphs. So a final natural question is: Problem 34. Find combinatorial algorithms to determine ω(G), ω c (G), χ c (G), and χ(G) for circular-perfect graphs G in polynomial time.

A first step in this direction would be to find such algorithms for subclasses of circular-perfect graphs, including perfect graphs themself.

Figure 1 :

 1 Figure 1: The circular cliques on nine vertices.

  17] as χ-bound graphs: A family G of graphs is called χ-bound with χ-binding function b if χ(G ) ≤ b(ω(G )) holds for all induced subgraphs G of G ∈ G. Thus this concept uses functions in the clique number ω(G) as upper bound on the chromatic number χ(G).

Figure 2 :

 2 Figure 2: An interlaced odd hole

Theorem 16 (

 16 [START_REF] Bachoc | On the theta number of powers of cycle graphs[END_REF]). Let G be a circular-perfect graph with circular-chromatic number k/d. Ifd ≥ 3 and k ≥ 4d 3 /π then ϑ(G) ≥ k d -4eπ 2 3 d k .Hence, for d fixed,

Figure 4 :

 4 Figure 4: Minimum weighted coloring of the Petersen graph P with weights w = (2, . . . , 2) (labels correspond to colors).

Problem 30 .

 30 Is there a suitable polyhedron COL c (G) such that minimizing an objective function w T x over COL c (G) yields the weighted circular chromatic number χ c (G, w)? If yes, this leads to the following question: Problem 31. Does COL f (G) coincide with COL c (G) if (and only if) G is star-superperfect?