Cographs which are cover-incomparability graphs of posets (Q2351716): Difference between revisions

If \(P=(V,\leq)\) is a poset, then its cover-incomparability graph \(G_P\) has \(V\) as its vertex set, and \(uv\) is an edge of \(G_P\) if \(u \triangleleft v\), \(v \triangleleft u\), or \(u\) and \(v\) are incomparable. In this paper the authors first consider cover-incomparability graphs within the class of cographs, consisting of graphs with no induced paths on 4 vertices. They prove that chordal cographs that are also cover-incomparability graphs, are characterized by having at most two maximal cliques. Then, the class of all cographs that are cover-incomparability graphs is characterized. Further, a forbidden isometric subposet characterization is proved for posets whose cover-incomparability graph is a cograph. As a conclusion, some families and properties of chordal-incomparability graphs are considered, pointing out that their complete characterization remains an open problem.