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

03/13/2022

∙

by   Alexey Barsukov, et al.

∙

0

∙

share

We show that the Max-Cut problem is NP-complete on interval graphs of interval count two.