Cover-incomparability graphs and chordal graphs
| Autor: | Manoj Changat, Joseph Mathews, Antony Mathews, Boštjan Brešar, Tanja Gologranc |
|---|---|
| Rok vydání: | 2010 |
| Předmět: |
Discrete mathematics
Block graph Applied Mathematics Interval graph Underlying graph Combinatorics Chordal graph Indifference graph Mathematics::Logic Pathwidth Poset Outerplanar graph Discrete Mathematics and Combinatorics Cograph Split graph Computer Science::Formal Languages and Automata Theory Mathematics |
| Zdroj: | Discrete Applied Mathematics. 158(16):1752-1759 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2010.07.001 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect