Abstract
We give a closed formula for Lovász’s theta number of the powers of cycle graphs C d−1 k 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 d k .
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
C. Berge: Färbungen von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind, Wiss. Zeitschrift der Martin-Luther-Universität Halle-Wittenberg (1961), 114–115.
T. Bohman: A limit theorem for the Shannon capacities of odd cycles II, Proceedings of the AMS 133 (2005), 537–543.
J. A. Bondy and P. Hell: A note on the star chromatic number, J. Graph Theory 14 (1990), 479–482.
V. E. Brimkov, B. Codenotti, V. Crespi and M. Leoncini: On the Lovász number of certain circular graphs, Lecture Notes in Computer Science 1767 (2000), 291–305.
P. Delsarte: An algebraic approach to the association schemes of coding theory, Philips Res. Rep. Suppl. (1973).
M. Grötschel, L. Lovász and A. Schrijver: The ellipsoid method and its consequences in combinatorial optimization, Combinatorica 2 (1981), 169–197.
S. Lang: Algebraic Number Theory, Graduate Texts in Mathematics 110, Springer.
L. Lovász: On the Shannon capacity of a graph, IEEE Trans. Inform. Theory IT-25 (1979), 1–5
A. Pêcher and A. K. Wagler: Clique and chromatic number of circular-perfect graphs, ISCO’10, Tunisia — Electronic Notes in Discrete Mathematics 36 (2010), 199–206.
A. Pêcher and A. K. Wagler: Polynomial time computability of some graph parameters for superclasses of perfect graphs, International Journal of Mathematics in Operational Research (to appear).
G. Szegő: Orthogonal polynomials, American Mathematical Society, 1939.
L. Vandenberghe and S. Boyd: Semidefinite programming, SIAM Review 38 (1996), 49–95.
A. Vince: Star chromatic number, J. Graph Theory 12 (1988), 551–559.
X. Zhu: Circular perfect graphs, J. Graph Theory 48 (2005), 186–209.
X. Zhu: Recent developments in circular colouring of graphs, Topics in Discrete Mathematics (2006), 497–550.
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by the ANR/NSC project GraTel ANR-09-blan-0373-01, NSC98-2115-M-002-013-MY3 and NSC99-2923-M-110-001-MY3.
Rights and permissions
About this article
Cite this article
Bachoc, C., Pêcher, A. & Thiéry, A. On the theta number of powers of cycle graphs. Combinatorica 33, 297–317 (2013). https://doi.org/10.1007/s00493-013-2950-x
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00493-013-2950-x