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.