Maximum Cut on Interval Graphs of Interval Count Two is NP-complete

Alexey Barsukov, Bodhayan Roy

An interval graph has interval count $\ell$ if it has an interval model, where among every $\ell +1$ intervals there are two that have the same length. Maximum Cut on interval graph…