Fiche du document
1 décembre 2013
- handle: 10670/1.rnugyd
- hal: hal-01003633
- ARXIV: 1103.0444
- doi: 10.1007/s00493-013-2950-x
Ce document est lié à :
info:eu-repo/semantics/altIdentifier/arxiv/1103.0444
Ce document est lié à :
info:eu-repo/semantics/altIdentifier/doi/10.1007/s00493-013-2950-x
info:eu-repo/semantics/OpenAccess
Sujets proches
Plots (Diagrams) Graphs Diagrams, charts, etc Graphics GraphsCiter ce document
Christine Bachoc et al., « On the theta number of powers of cycle graphs », HAL-SHS : sciences de l'information, de la communication et des bibliothèques, ID : 10.1007/s00493-013-2950-x
Métriques
Partage / Export
Résumé
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$.