# Lovász theta-function of graphs¶

AUTHORS:

• Dima Pasechnik (2015-06-30): Initial version

REFERENCE:

[Lov1979]

## Functions¶

sage.graphs.lovasz_theta.lovasz_theta(graph)

Return the value of Lovász theta-function of graph

For a graph $$G$$ this function is denoted by $$\theta(G)$$, and it can be computed in polynomial time. Mathematically, its most important property is the following:

$\alpha(G)\leq\theta(G)\leq\chi(\overline{G})$

with $$\alpha(G)$$ and $$\chi(\overline{G})$$ being, respectively, the maximum size of an independent set set of $$G$$ and the chromatic number of the complement $$\overline{G}$$ of $$G$$.

Note

• Implemented for undirected graphs only. Use to_undirected to convert a digraph to an undirected graph.
• This function requires the optional package csdp, which you can install with sage -i csdp.

EXAMPLES:

sage: C = graphs.PetersenGraph()
sage: C.lovasz_theta()                             # optional csdp
4.0
sage: graphs.CycleGraph(5).lovasz_theta()          # optional csdp
2.236068