Abstract
In this paper we continue investigations of cover-incomparability graphs of finite partially ordered sets (see Brešar et al. Order 25:335–347 2008; Brešar et al. Discret. Appl. Math. 158:1752–1759 2010; Brešar et al. Order 32(2):179–187 2015; Brešar et al. 2014 and Maxová et al. Order 26:229–236 2009; Maxová and Turzík 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 Brešar et al. (Order 25:335–347 2008) and Brešar 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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Brešar, B., Changat, M., Klavžar, S., Kovše, M., Mathews, J., Mathews, A.: Cover-Incomparability Graphs of posets. Order 25, 335–347 (2008)
Brešar, B., Changat, M., Gologranc, T., Mathews, J., Mathews, A.: Cover-incomparability graphs and chordal graphs. Discret. Appl. Math. 158, 1752–1759 (2010)
Brešar, B., Changat, M., Gologranc, T., Sukumaran, B.: Cographs which are cover-incomparability graphs of posets. Order 32(2), 179–187 (2015)
Brešar, B., Changat, M., Gologranc, T., Kovše, M., Sukumaran, B.: Cover-incomparability graphs and 2-colored diagrams of posets, Taiwanese Journal of Mathematics (2014)
Maxová, J., Pavlíková, P., Turzík, D.: On the complexity of cover-incomparability graphs of posets. Order 26, 229–236 (2009)
Maxová, J., Turzík, D.: Which distance-hereditary graphs are cover-incomparability graphs? Discret. Appl. Math. 161, 2095–2100 (2013)
Maxová, J., Dubcová, M., Pavlíková, P., Turzík, D.: Which k-trees are cover-incomparability graphs? Discret. Appl. Math. 167, 222–227 (2014)
Acknowledgments
The authors would like to thank Boštjan Brešar, Sandi Klavžar, and the editor of this paper for many valuable comments and suggestions regarding this paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Jan Bok would like to acknowledge the support by the Center of Excellence -ITI (P202/12/G061 of GAČR). Jan Bok was also partly supported by the project GAUK 1158216 and GAUK 1334217.
Rights and permissions
About this article
Cite this article
Bok, J., Maxová, J. Characterizing Subclasses of Cover-Incomparability Graphs by Forbidden Subposets. Order 36, 349–358 (2019). https://doi.org/10.1007/s11083-018-9470-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11083-018-9470-7