New descriptions of the Lovász number, and the weak sandwich theorem

Ujvári Miklós: New descriptions of the Lovász number, and the weak sandwich theorem. In: Acta cybernetica, (20) 4. pp. 499-513. (2012)

[thumbnail of actacyb_20_4_2012_3.pdf]
Cikk, tanulmány, mű

Download (165kB) | Preview


In 1979, L. Lovász introduced the concept of an orthonormal representation of a graph, and also a related value, now popularly known as the Lovász number of the graph. One of the remarkable properties of the Lovász number is that it lies sandwiched between the stability number of the graph and the chromatic number of the complementary graph. This fact is called the sandwich theorem. In this paper, using new descriptions of the Lovász number and linear algebraic lemmas we give three proofs for a weaker version of the sandwich theorem.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 2012
Volume: 20
Number: 4
ISSN: 0324-721X
Page Range: pp. 499-513
Language: English
Place of Publication: Szeged
Related URLs:
DOI: 10.14232/actacyb.20.4.2012.2
Uncontrolled Keywords: Számítástechnika, Kibernetika, Matematika
Additional Information: Bibliogr.: p. 512-513. ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.01. Mathematics
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2016. Oct. 17. 10:38
Last Modified: 2022. Jun. 17. 14:49

Actions (login required)

View Item View Item