Maximum cut on interval graphs of interval count four is NP-complete

Celina M. H. de Figueiredo, Alexsander A. de Melo, Fabiano S. Oliveira +1

The computational complexity of the MaxCut problem restricted to interval graphs has been open since the 80's, being one of the problems proposed by Johnson on his Ongoing Guide to…