Max \(k\)-cut and the smallest eigenvalue

DOI10.1016/j.laa.2016.04.019zbMath1338.05168arXiv1604.02088OpenAlexW2964166578MaRDI QIDQ286169

F. Blanchet-Sadri, M. Dambrine

Publication date: 20 May 2016

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1604.02088

zbMATH Keywords

chromatic numberlargest eigenvalues\(\max k\)-cutlargest Laplacian eigenvaluesmallest adjacency eigenvalue

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items

Computational study of valid inequalities for the maximum \(k\)-cut problem, A class of spectral bounds for max \(k\)-cut, On graphs with eigenvectors in \(\{-1,0,1\}\) and the max \(k\)-cut problem, A spectral partitioning algorithm for maximum directed cut problem

Cites Work

• New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph
• Chromatic number and spectral radius
• Laplacian eigenvalues and the maximum cut problem
• Max Cut and the Smallest Eigenvalue
• Unnamed Item
• Unnamed Item