New bounds for the max-$k$-cut and chromatic number of a graph

Abstract

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 any graph. This bound is exploited to derive a new eigenvalue bound on the chromatic number of a graph. For regular graphs, the new bound on the chromatic number is the same as the well-known Hoffman bound; however, the two bounds are incomparable in general. We prove that the eigenvalue bound for the max-$k$-cut is tight for several classes of graphs. We investigate the presented bounds for specific classes of graphs, such as walk-regular graphs, strongly regular graphs, and graphs from the Hamming association scheme.

References in corpus (2)

• Symmetry groups, semidefinite programs, and sums of squares
• Semidefinite programming and eigenvalue bounds for the graph partition problem

Cited by in corpus (5)

• Eigenvalues of Cayley graphs
• Max-cut and extendability of matchings in distance-regular graphs
• New Eigenvalue Bound for the Fractional Chromatic Number
• The maximum $k$-colorable subgraph problem and related problems
• Max k-cut and the smallest eigenvalue