On the complexity of cover-incomparability graphs of posets

DOI10.1007/s11083-009-9117-9zbMath1172.05049OpenAlexW2113780681MaRDI 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

graphposetNP-completecocomparability graphtransitive orientation

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (9)

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

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

This page was built for publication: On the complexity of cover-incomparability graphs of posets