On the complexity of cover-incomparability graphs of posets
type: Item
instance of: scholarly article
title: On the complexity of cover-incomparability graphs of posets
zbMATH Open document ID: 1172.05049
author: Jana Maxová
author: Pavla Pavlíková
author: Daniel Turzík
published in: Order
publication date: 2009-09-14T00:00:00Z
review text: The cover-incomparability graph (or C-I graph) \(G\) of a poset \(P=(V,\leq)\) has vertex set \(V\), and two vertices \(x\) and \(y\) are adjacent in \(G\) if \(x\) covers \(y\) in \(P\), or \(y\) covers \(x\) in \(P\), or \(x\) and \(y\) are incomparable in \(P\), see \textit{B. Brešar}, \textit{M. Changat}, \textit{S. Klavžar}, \textit{M. Kovše}, \textit{J. Mathews}, and \textit{A. Mathews} [Order 25, No. 4, 335--347 (2008; Zbl 1219.06004)]. The recognition problem for C-I graphs is NP-complete, but the induced subgraphs of C-I graphs form exactly the class of cocomparability graphs, and can therefore be recognised in linear time, see \textit{R. M. McConnell} and \textit{J. P. Spinrad} [Discrete Math.\ 201, No.\,1-3, 189--241 (1999; Zbl 0933.05146)].
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C62
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5603894
zbMATH Keywords: poset
zbMATH Keywords: graph
zbMATH Keywords: transitive orientation
zbMATH Keywords: cocomparability graph
zbMATH Keywords: NP-complete
MaRDI profile type: Publication
full work available at URL: s11083-009-9117-9
OpenAlex ID: W2113780681
cites work: Cover-incomparability graphs of posets
cites work: On the complexity of diagram testing
cites work: Transitiv orientierbare Graphen
cites work: Q4198056
cites work: Algorithmic graph theory and perfect graphs
cites work: Q3880849
cites work: Complexity of diagrams
cites work: Q4852554
cites work: Q4152571
cites work: Q4393243
DOI: 10.1007/S11083-009-9117-9
Recommended article: Cover-incomparability graphs of posets
Recommended article: Cover-incomparability graphs and 2-colored diagrams of posets
Recommended article: Cographs which are cover-incomparability graphs of posets
Recommended article: Q4474120
Recommended article: Cover-incomparability graphs and chordal graphs
Recommended article: Comparability graphs among cover-incomparability graphs
Recommended article: Composition and product of cover-incomparability graphs
Recommended article: Incidence posets and cover graphs
Recommended article: On the dimension of posets with cover graphs of treewidth 2
Recommended article: Characterizing subclasses of cover-incomparability graphs by forbidden subposets
description: scientific article; zbMATH DE number 5603894