Friday, 15:15 - 15:40 h, Room: H 3004


Arnaud Pecher
On the theta number of powers of cycle graphs

Coauthors: Christine Bachoc, Alain Thiery


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 Ckd-1 and of their complements, the circular complete graphs Kk/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.


Talk 1 of the invited session Fri.3.H 3004
"Packing, covering and domination II" [...]
Cluster 2
"Combinatorial optimization" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. Since its introduction in the market buying Buy Generic Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.