# zbMATH — the first resource for mathematics

The sandwich theorem. (English) Zbl 0810.05065
Electron. J. Comb. 1, Article A1, 48 p. (1994); printed version J. Comb. 1, 1-48 (1994).
Summary: This report contains expository notes about a function $$\theta(G)$$ that is popularly known as the Lovász number of a graph $$G$$. There are many ways to define $$\theta(G)$$, and the surprising variety of different characterizations indicates in itself that $$\theta(G)$$ should be interesting. But the most interesting property of $$\theta(G)$$ is probably the fact that it can be computed efficiently, although it lies “sandwiched” between other classic graph numbers whose computation is NP-hard. I have tried to make these notes self-contained so that they might serve as an elementary introduction to the growing literature on Lovász’s fascinating function.

##### MSC:
 05C15 Coloring of graphs and hypergraphs 05C78 Graph labelling (graceful graphs, bandwidth, etc.) 52B55 Computational aspects related to convexity 68R10 Graph theory (including graph drawing) in computer science
Full Text: