Charles Explorer logo
🇬🇧

Characterizing Subclasses of Cover-Incomparability Graphs by Forbidden Subposets

Publication at Faculty of Mathematics and Physics |
2019

Abstract

In this paper we continue investigations of cover-incomparability graphs of finite partially ordered sets (see Brear et al. Order 25:335-347 2008; Brear et al.

Discret. Appl.

Math. 158:1752-1759 2010; Brear et al. Order 32(2):179-187 2015; Brear et al. 2014 and Maxova et al.

Order 26:229-236 2009; Maxova and Turzik Discret. Appl.

Math. 161:2095-2100 2013). 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 Brear et al. (Order 25:335-347 2008) and Brear et al. (Order 32(2):179-187 2015) are not valid as presented. Here we provide examples, investigate the root of the difficulties, and formulate and prove valid revisions of these characterizations.