Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419622 | Discrete Applied Mathematics | 2013 | 6 Pages |
Abstract
In this paper we deal with cover–incomparability graphs of posets, or briefly C–I graphs. These are graphs derived from posets as the edge-union of their cover graph and their incomparability graph. We answer two recently posed open questions. Which distance-hereditary graphs are C–I graphs? Which Ptolemaic (i.e. chordal distance-hereditary) graphs are C–I graphs? It follows that C–I graphs can be recognized efficiently in the class of all distance-hereditary graph whereas recognizing C–I graphs in general is known to be NP-complete.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jana Maxová, Daniel Turzík,