MaxCut on Permutation Graphs is NP-complete
arXiv:2202.13955
Abstract
In this paper, we prove that the MaxCut problem is NP-complete on permutation graphs, settling a long-standing open problem that appeared in the 1985 column of the "Ongoing Guide to NP-completeness" by David S. Johnson.