A characterization of interval orders with semiorder dimension two

DOI10.1016/J.DAM.2021.02.010MaRDI QIDQ2022521zbMATH OpenOpenAlexFDO

Authors 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

dimensionpartially ordered setsinterval ordersemiorder

Mathematics Subject Classification ID

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

Recommendations

• Semi-order dimension two is a comparability invariant
• Dimensions of split semiorders
• On the complexity of interval orders and semiorders
• A recognition algorithm for orders of interval dimension two
• scientific article; zbMATH DE number 1554938

Cites work

• scientific article; zbMATH DE number 3853140 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• A recognition algorithm for orders of interval dimension two
• An intersection model for multitolerance graphs: efficient algorithms and hierarchy
• On powers of m-trapezoid graphs
• On the 2-Chain Subgraph Cover and Related Problems
• On the non-unit count of interval graphs
• Proper and unit bitolerance orders and graphs
• Proper and unit tolerance graphs
• Proper and unit trapezoid orders and graphs
• Semi-order dimension two is a comparability invariant
• Simple inductive proofs of the Fishburn and Mirkin theorem and the Scott-Suppes theorem
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The dimension of semiorders
• The recognition of tolerance and bounded tolerance graphs
• Trapezoid graphs and generalizations, geometry and algorithms
• Trapezoid graphs and their coloring
• Triangulating multitolerance graphs
• Vertex splitting and the recognition of trapezoid graphs

Cited in

(5)

• A characterization of PQI interval orders.
• Inductive characterizations of finite interval orders and semiorders
• Semi-order dimension two is a comparability invariant
• A simple proof characterizing interval orders with interval lengths between 1 and \(k\)
• Hereditary semiorders and enumeration of semiorders by dimension

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2022521)