 Lovász number

The Lovász number of a finite simple graph is the semidefinite program valuewhere $J$ is the all-ones matrix. Its value on the complement graph gives a lower bound for the chromatic number.

The Lovász number, denoted as \( \vartheta(G) \), is a graph parameter associated with a simple undirected graph \( G \). It is a meaningful quantity in the context of both combinatorial optimization and information theory. The Lovász number can be interpreted in several ways and is particularly important in the study of graph coloring, independent sets, and the performance of certain algorithms.