Article ID Journal Published Year Pages File Type
418783 Discrete Applied Mathematics 2014 6 Pages PDF
Abstract

In this paper we deal with cover–incomparability graphs of posets. It is known that the class of cover–incomparability graphs is not closed on induced subgraphs which makes the study of structural properties of these graphs difficult. In this paper we introduce the notion of s-subgraph   which enables us to define forbidden s-subgraphs (i.e. graphs that cannot appear as s-subgraphs of any cover–incomparability graph). We show that the family of minimal forbidden s-subgraphs is infinite even for cover–incomparability unit-interval graphs. Using the notion of s-subgraph we also answer the question which kk-trees are cover–incomparability graphs and which chordal graphs without K4K4 are cover–incomparability graphs.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , ,