Sandwich Theorem

The Lovász number  of a graph  satisfies

where  is the clique number,  is the chromatic number of , and  is the graph complement of . Furthermore,  can be computed efficiently despite the fact that the computation of the two numbers it lies between is an NP-hard problem.

The squeezing theorem is also sometimes known as the sandwich theorem.

REFERENCES

Grötschel, M.; Lovász, L.; and Schrijver, A. "The Ellipsoid Method and Its Consequences in Combinatorial Optimization." Combinatorica 1, 169-197, 1981.

Knuth, D. E. "The Sandwich Theorem." Electronic J. Combinatorics 1, No. 1, A1, 1-48, 1994. http://www.combinatorics.org/Volume_1/Abstracts/v1i1a1.html.