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" [...]


  pay day loans . Since its introduction in the market buying 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.