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