Lovász theta-function of graphs

AUTHORS:

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

REFERENCE:

[Lov1979]

Functions

sage.graphs.lovasz_theta.lovasz_theta(graph)[source]

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\).

For more information, see the Wikipedia article Lovász_number.

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

>>> from sage.all import *
>>> C = graphs.PetersenGraph()
>>> C.lovasz_theta()                             # optional - csdp
4.0
>>> graphs.CycleGraph(Integer(5)).lovasz_theta()          # optional - csdp
2.236068