Lovász theta-function of graphs#
AUTHORS:
Dima Pasechnik (2015-06-30): Initial version
REFERENCE:
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 thechromatic number
of thecomplement
\(\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 withsage -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