On the complexity of cover-incomparability graphs of posets

DOI10.1007/s11083-009-9117-9zbMath1172.05049MaRDI QIDQ841163

Pavla Pavlíková, Daniel Turzík, Jana Maxová

Publication date: 14 September 2009

Published in: Order (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11083-009-9117-9

zbMATH Keywords

graph; poset; NP-complete; cocomparability graph; transitive orientation

Mathematics Subject Classification ID

06A07: Combinatorics of partially ordered sets

05C75: Structural characterization of families of graphs

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C62: Graph representations (geometric and intersection representations, etc.)

Related Items

Composition and product of cover-incomparability graphs, Comparability graphs among cover-incomparability graphs, Cover-incomparability graphs and chordal graphs, Ptolemaic and chordal cover-incomparability graphs, Characterizing subclasses of cover-incomparability graphs by forbidden subposets, Cographs which are cover-incomparability graphs of posets, Which \(k\)-trees are cover-incomparability graphs?, Which distance-hereditary graphs are cover-incomparability graphs?, Ptolemaic and planar cover-incomparability graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cover-incomparability graphs of posets
• Complexity of diagrams
• On the complexity of diagram testing
• Algorithmic graph theory and perfect graphs
• Transitiv orientierbare Graphen