首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号