There are several theorems known as the "sandwich theorem."
In calculus, the squeeze theorem is also sometimes known as the sandwich theorem.
In graph theory, the sandwich theorem states that the Lovász number 
of a graph 
satisfies
 |
(1)
|
where 
is the clique number, 
is the chromatic number
of 
,
and 
is the graph complement of 
. This can be rewritten by changing the role of graph complements,
giving
 |
(2)
|
which can be written using 
with 
the independence number and 
the clique
covering number as
 |
(3)
|
Furthermore, 
can be computed efficiently despite the fact that the computation of the two numbers
it lies between is an NP-hard problem.
