max-hBccut – Optimization Online

New bounds for the max-hBccut and chromatic number of a graph

Published: 2015/03/23

Combinatorial Optimization, Semi-definite Programming association schemes, chromatic number, hamming graphs, laplacian eigenvalues, max-hBccut, semidefinite programming, strongly regular graphs, walk-regular graphs

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