On the theta number of powers of cycle graphs
BACHOC, Christine
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
BACHOC, Christine
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
< Reduce
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Language
en
Article de revue
This item was published in
Combinatorica. 2013-12-01, vol. 33, n° 3, p. 297-317
Springer Verlag
English Abstract
We give a closed formula for Lovász's theta number of the powers of cycle graphs $C_k^d$ and of their complements, the circular complete graphs $K_{k/d}$. As a consequence, we establish that the circular chromatic number ...Read more >
We give a closed formula for Lovász's theta number of the powers of cycle graphs $C_k^d$ 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. We also derive an asymptotic estimate for the theta number of $C_k^d$.Read less <
ANR Project
/ - ANR-09-BLAN-0373
Origin
Hal imported