On the complexity of cover-incomparability graphs of posets (Q841163): Difference between revisions

The cover-incomparability graph (or C-I graph) \(G\) of a poset \(P=(V,\leq)\) has vertex set \(V\), and two vertices \(x\) and \(y\) are adjacent in \(G\) if \(x\) covers \(y\) in \(P\), or \(y\) covers \(x\) in \(P\), or \(x\) and \(y\) are incomparable in \(P\), see \textit{B. Brešar}, \textit{M. Changat}, \textit{S. Klavžar}, \textit{M. Kovše}, \textit{J. Mathews}, and \textit{A. Mathews} [Order 25, No. 4, 335--347 (2008; Zbl 1219.06004)]. The recognition problem for C-I graphs is NP-complete, but the induced subgraphs of C-I graphs form exactly the class of cocomparability graphs, and can therefore be recognised in linear time, see \textit{R. M. McConnell} and \textit{J. P. Spinrad} [Discrete Math.\ 201, No.\,1-3, 189--241 (1999; Zbl 0933.05146)].