Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418783 | Discrete Applied Mathematics | 2014 | 6 Pages |
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
Jana Maxová, Miroslava Dubcová, Pavla Pavlíková, Daniel Turzík,