Which distance-hereditary graphs are cover–incomparability graphs? |
| |
Authors: | Jana Maxová Daniel Turzík |
| |
Institution: | Department of Mathematics, Institute of Chemical Technology, Prague, Technická 5, 166 28 Praha 6, Czech Republic |
| |
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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|