On the theta number of powers of cycle graphs |
| |
| Authors: | Christine Bachoc Arnaud Pêcher Alain Thiéry |
| |
| Affiliation: | 1. Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux I, 33405, Talence, France
2. Laboratoire Bordelais de Recherche Informatique (LaBRI) / INRIA Sud-Ouest, Université Bordeaux I, 33405, Talence, France
|
| |
| Abstract: | We give a closed formula for Lovász’s theta number of the powers of cycle graphs C k d?1 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 . |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
