Characterizing subclasses of cover-incomparability graphs by forbidden subposets

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75) Combinatorics of partially ordered sets (06A07)

Abstract: In this paper we continue investigations of cover-incomparability graphs of finite partially ordered sets (see cite{Bres,Bres2,Bres3,Bres4} and cite{Max,MaxDH}). We consider in some detail the distinction between cover-preserving subsets and isometric subsets of a partially ordered set. This is critical to understanding why forbidden subposet characterizations of certain classes of cover-incomparability graphs in cite{Bres} and cite{Bres3} are not valid as presented. Here we provide examples, investigate the root of the difficulties, and formulate and prove valid revisions of these characterizations.

Review text

The cover-incomparability graph of a poset is a graph whose vertex set is the vertex set of the poset and where there is an edge between \(x\) and \(y\) if \(x\) covers \(y\) or \(y\) covers \(x\) or \(x\) and \(y\) are incomparable. The authors consider various statements which have recently been made relating the structure of cover-incomparability graphs to forbidden subposets of the poset. They show that these statements are untrue, the confusion possibly having arisen from confusing two special types of subposet -- the isometric subposets and the weaker notion of \(\prec\)-preserving subposet which has to replace the notion of isometric subposet in the statements. The authors also provide corrected versions of these statements

Recommendations

Cites work

Cited in

(9)

This page was built for publication: Characterizing subclasses of cover-incomparability graphs by forbidden subposets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2314427)