Edwin van Dam We consider several semidefinite programming relaxations for the max-$k$-cut problem, with increasing complexity. The optimal solution of the weakest presented semidefinite programming relaxation has a closed form expression that includes the largest Laplacian eigenvalue of the graph under consideration. This is the first known eigenvalue bound for the max-$k$-cut when $k>2$ that is applicable to … Read more
The graph partition problem is the problem of partitioning the vertex set of a graph into a fixed number of sets of given sizes such that the total weight of edges joining different sets is optimized. In this paper we simplify a known matrix-lifting semidefinite programming relaxation of the graph partition problem for several classes … Read more
We derive a new lower bound for the bandwidth of a graph that is based on a new lower bound for the minimum cut problem. Our new semide finite programming relaxation of the minimum cut problem is obtained by strengthening the well-known semide nite programming relaxation for the quadratic assignment problem by fixing two vertices in the … Read more