Cover-incomparability graphs and chordal graphs |
| |
Authors: | Boštjan Brešar Manoj Changat |
| |
Institution: | a Faculty of Natural Sciences and Mathematics, University of Maribor, Sloveniab C-GRaF, Department of Futures Studies, University of Kerala, Trivandrum-695034, Indiac Institute of Mathematics, Physics and Mechanics, Ljubljana, Sloveniad Department of Mathematics, St.Berchmans College, Changanassery - 686 101, Kerala, India |
| |
Abstract: | 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. |
| |
Keywords: | Poset Underlying graph Chordal graph Split graph Block graph |
本文献已被 ScienceDirect 等数据库收录! |
|