## Invited Session Fri.3.H 3004

#### Friday, 15:15 - 16:45 h, Room: H 3004

**Cluster 2: Combinatorial optimization** [...]

### Packing, covering and domination II

**Chair: Annegret K. Wagler**

**Friday, 15:15 - 15:40 h, Room: H 3004, Talk 1**

**Arnaud Pecher**

On the theta number of powers of cycle graphs

**Coauthors: Christine Bachoc, Alain Thiery**

**Abstract:**

A main result of combinatorial optimization is that clique and chromatic number of a perfect graph are computable in polynomial time (Grötschel, Lovász and Schrijver 1981).

We give a closed formula for Lovász's theta number of the powers of

cycle graphs *C*_{k}^{d-1} and of their complements, the circular complete graphs *K*_{k/d}. As a consequence, we establish that the circular-chromatic number of a circular-perfect graph is computable in

polynomial time, which extends the above result from the chromatic number to the circular-chromatic number, and from perfect graphs to the superclass of circular-perfect graphs.

**Friday, 15:45 - 16:10 h, Room: H 3004, Talk 2**

**Silvia María Bianchi**

The disjunctive rank of the stable set polytope of web graphs

**Coauthors: Mariana S. Escalante, Maria S. Montelar**

**Abstract:**

We consider the behavior of the disjunctive operator defined by Balas, Ceria and Cornuéjols, over the clique relaxation of the stable set problem on webs. The disjunctive rank of a graph is the minimum number of steps of this procedure needed to obtain the convex hull of integer solutions in it. In this work we obtain the disjunctive rank of all webs, when starting from the clique relaxation. We find that almost every web *W*_{n}^{k} attain the upper bound of its disjunctive rank,i.e. *k*, except for those of the form *W*_{3k+r}^{k} with *r=0* or *r=1*, that requires *k-2* or *k-1* steps, respectively.

Our results allow us to obtain bounds for the disjunctive rank of a larger class of graphs such as quasi-line graphs and their complements, the near-bipartite graphs.

**Friday, 16:15 - 16:40 h, Room: H 3004, Talk 3**

**Luis Miguel Torres**

On the Chvátal-closure of the fractional set covering polyhedron of circulant matrices

**Coauthor: Paola Tolomei**

**Abstract:**

The set covering polyhedron *Q*^{*}(C_{n}^{k}) related to circulant *0,1*-matrices has been the object of several recent studies. It has been conjectured that the Chvátal-rank of its fractional relaxation *Q(C*_{n}^{k}) is equal to *1*. In 2009, Argiroffo and Bianchi characterized all vertices of *Q(C*_{n}^{k}). Building upon their characterization, we investigate the first Chvátal-closure of this polyhedron. Our aim is to obtain a complete linear description, by considering the integral generating sets of the cones spanned by the normal vectors of the facets containing each vertex of *Q(C*_{n}^{k}). In this talk we present the results obtained so far for some classes of vertices. In particular, our construction yields a counterexample to a conjecture that all facets of *Q*^{*}(C_{n}^{k}) are given by boolean, nonnegative, and so-called minor inequalities having only coefficients in *{1,2}*. At the same time, we motivate why a weaker version of this conjecture might still hold.