Spectral bounds for the independence ratio and the chromatic number of an operator

We define the independence ratio and the chromatic number for bounded, self-adjoint operators on an L^2-space by extending the definitions for the adjacency matrix of finite graphs. In analogy to the Hoffman bounds for finite graphs, we give bounds for these parameters in terms of the numerical range of the operator. This provides a theoretical … Read more

Min-Max Theorems Related to Geometric Representations of Graphs and their SDPs

Lovasz proved a nonlinear identity relating the theta number of a graph to its smallest radius hypersphere embedding where each edge has unit length. We use this identity and its generalizations to establish min-max theorems and to translate results related to one of the graph invariants above to the other. Classical concepts in tensegrity theory … Read more

Copositive programming motivated bounds on the stability and the chromatic numbers

The Lovász theta number of a graph G can be viewed as a semidefinite programming relaxation of the stability number of G. It has recently been shown that a copositive strengthening of this semidefinite program in fact equals the stability number of G. We introduce a related strengthening of the Lovász theta number toward the … Read more

On the Lovász theta-number of almost regular graphs with application to Erdös–Rényi graphs

We consider k-regular graphs with loops, and study the Lovász theta-numbers and Schrijver theta’-numbers of the graphs that result when the loop edges are removed. We show that the theta-number dominates a recent eigenvalue upper bound on the stability number due to Godsil and Newman [C.D. Godsil and M.W. Newman. Eigenvalue bounds for independent sets. … Read more

Copositive programming motivated bounds on the stability and the chromatic number

The Lovasz theta number of a graph G can be viewed as a semidefinite programming relaxation of the stability number of G. It has recently been shown that a copositive strengthening of this semidefinite program in fact equals the stability number of G. We introduce a related strengthening of the Lovasz theta number toward the … Read more

A semidefinite programming based heuristic for graph coloring

The Lovasz theta function is a well-known polynomial lower bound on the chromatic number. . Any near optimal solution of its semidefinite programming formulation carries valuable information on how to color the graph. A self-contained presentation of the role of this formulation in obtaining heuristics for the graph coloring problem is presented. Citation Submitted to … Read more

Semidefinite programming relaxations for graph coloring and maximal clique problems

The semidefinite programming formulation of the Lovasz theta number does not only give one of the best polynomial simultaneous bounds on the chromatic number and the clique number of a graph, but also leads to heuristics for graph coloring and extracting large cliques. This semidefinite programming formulation can be tightened toward either number by adding … Read more