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

Research output: Contribution to journalArticleScientificpeer-review

15 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)216 - 234
Number of pages18
JournalLinear Algebra and its Applications
Publication statusPublished - 1 Jan 2016


  • max-k-cut
  • chromatic number
  • semidefinite programming
  • Laplacian eigenvalues
  • walk-regular graphs
  • association schemes
  • strongly regular graphs
  • Hamming graphs


Dive into the research topics of 'New bounds for the max-k-cut and chromatic number of a graph'. Together they form a unique fingerprint.

Cite this