Which distance-hereditary graphs are coverincomparability graphs?
In this paper we deal with coverincomparability graphs of posets, or briefly CI 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 CI graphs? Which Ptolemaic (i.e. chordal distance-hereditary) graphs are CI graphs? It follows that CI graphs can be recognized efficiently in the class of all distance-hereditary graph whereas recognizing CI graphs in general is known to be NP-complete.
distance-hereditary graphs graph poset ptolemaic graphs