Polarity and Monopolarity of 3-colourable comparability graphs
classification
💻 cs.CC
math.CO
keywords
monopolaritycolourablecomparabilitygraphspolaritynp-completegraphinput
read the original abstract
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 comparability graph. We start by presenting a construction reducing $1$-$3$-SAT to monopolarity of $3$-colourable comparability graphs. Then we show that polarity is at least as hard as monopolarity for input graphs restricted to a fixed disjoint-union-closed class. We conclude the paper by stating that both polarity and monopolarity of $3$-colourable comparability graphs are NP-complete problems.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.