A characterization of interval orders with semiorder dimension two

DOI10.1016/j.dam.2021.02.010zbMath1462.06001OpenAlexW3155127207MaRDI QIDQ2022521

Alexander Apke, Rainer Schrader

Publication date: 29 April 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2021.02.010

zbMATH Keywords

dimensioninterval ordersemiorderpartially ordered sets

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Enumeration in graph theory (05C30)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the non-unit count of interval graphs
• Trapezoid graphs and generalizations, geometry and algorithms
• Trapezoid graphs and their coloring
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The dimension of semiorders
• Proper and unit bitolerance orders and graphs
• Triangulating multitolerance graphs
• Simple inductive proofs of the Fishburn and Mirkin theorem and the Scott-Suppes theorem
• Proper and unit tolerance graphs
• A recognition algorithm for orders of interval dimension two
• On powers of \(m\)-trapezoid graphs
• Proper and unit trapezoid orders and graphs
• Semi-order dimension two is a comparability invariant
• Vertex splitting and the recognition of trapezoid graphs
• The Recognition of Tolerance and Bounded Tolerance Graphs
• On the 2-Chain Subgraph Cover and Related Problems

This page was built for publication: A characterization of interval orders with semiorder dimension two