On the complexity of cover-incomparability graphs of posets
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)].
scientific article; zbMATH DE number 5603894
scientific article