Polarity and Monopolarity of $3$-colourable comparability graphs

Nikola Yolov

We sharpen the result that polarity and monopolarity are NP-complete problems by showing that they remain NP-complete if the input graph is restricted to be a $3$-colourable compar…