Lovász number

In graph theory, the Lovász number of a graph is a real number that is an upper bound on the Shannon capacity of the graph. It is also known as Lovász theta function and is commonly denoted by , using a script form of the Greek letter theta to contrast with the upright theta used for Shannon capacity. This quantity was first introduced by László Lovász in his 1979 paper On the Shannon Capacity of a Graph.

Accurate numerical approximations to this number can be computed in polynomial time by semidefinite programming and the ellipsoid method. The Lovász number of the complement of any graph is sandwiched between the chromatic number and clique number of the graph, and can be used to compute these numbers on graphs for which they are equal, including perfect graphs.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.