Optimization Online


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

Edwin van Dam(Edwin.vanDam***at***uvt.nl)
Renata Sotirov(r.sotirov***at***uvt.nl)

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.

Keywords: max-$k$-cut, chromatic number, semidefinite programming, Laplacian eigenvalues, walk-regular graphs, association schemes, strongly regular graphs, Hamming graphs

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Combinatorial Optimization


Download: [PDF]

Entry Submitted: 03/23/2015
Entry Accepted: 03/23/2015
Entry Last Modified: 03/23/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society