On the theta number of powers of cycle graphs
PÊCHER, Arnaud
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
PÊCHER, Arnaud
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
< Reduce
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Language
en
Document de travail - Pré-publication
English Abstract
We give a closed formula for Lovasz theta number of the powers of cycle graphs and of their complements, the circular complete graphs. As a consequence, we establish that the circular chromatic number of a circular perfect ...Read more >
We give a closed formula for Lovasz theta number of the powers of cycle graphs and of their complements, the circular complete graphs. 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 this theta number.Read less <
English Keywords
theta number
circular complete graph
circular perfect graph
ANR Project
/ - ANR-09-BLAN-0373
Origin
Hal imported