Lovász theta-function of graphs

AUTHORS:

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

REFERENCE:

[Lovasz1979]László Lovász, “On the Shannon capacity of a graph”, IEEE Trans. Inf. Th. 25(1979), 1-7.

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.

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 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

TEST:

sage: g = Graph()
sage: g.lovasz_theta() # indirect doctest
0