A class of spectral bounds for Max k-Cut

Miguel F Anjos, Jose Neto

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

In this paper we introduce a new class of bounds for the maximum -cut problem on undirected edge-weighted simple graphs. The bounds involve eigenvalues of the weighted adjacency matrix together with geometrical parameters. They generalize previous results on the maximum (2-)cut problem and we demonstrate that they can strictly improve over other eigenvalue bounds from the literature. We also report computational results illustrating the potential impact of the new bounds.
Original languageEnglish
Pages (from-to)12-24
Number of pages31
JournalDiscrete Applied Mathematics
Early online date14 Nov 2019
Publication statusPublished - 31 May 2020


Dive into the research topics of 'A class of spectral bounds for Max k-Cut'. Together they form a unique fingerprint.

Cite this