Spectral Approaches to Max-cut Problematic

We present a new spectral upper bound for the max-cut problem and compare it to the known Poljak-Delorme eigenvalue bound. Besides, we are discussing a recent spectral characterization of bipartite graphs and use it to propose a new and simple heuristic for finding a bipartite subgraph.