The system will be going down for regular maintenance. Please save your work and logout.
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