  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.
