Cover-incomparability graphs and chordal graphs

详细信息    查看全文

• 作者：Boš ; tjan Breš ; ar ; Manoj Changat ; Tanja Gologranc ; Joseph Mathews ; Antony Mathews
• 关键词：Poset ; Underlying graph ; Chordal graph ; Split graph ; Block graph
• 刊名：Discrete Applied Mathematics
• 出版年：2010
• 出版时间：28 August 2010
• 年：2010
• 卷：158
• 期：16
• 页码：1752-1759
• 全文大小：455 K

文摘

The problem of recognizing cover-incomparability graphs (i.e. the graphs obtained from posets as the edge-union of their covering and incomparability graph) was shown to be NP-complete in general [J. Maxová, P. Pavlíkova, A. Turzík, On the complexity of cover-incomparability graphs of posets, Order 26 (2009) 229–236], while it is for instance clearly polynomial within trees. In this paper we concentrate on (classes of) chordal graphs, and show that any cover-incomparability graph that is a chordal graph is an interval graph. We characterize the posets whose cover-incomparability graph is a block graph, and a split graph, respectively, and also characterize the cover-incomparability graphs among block and split graphs, respectively. The latter characterizations yield linear time algorithms for the recognition of block and split graphs, respectively, that are cover-incomparability graphs.