The paper studies the digraph versions of tolerance graphs, and in particular, the class of totally bounded bitolerance digraphs and several subclasses. It starts with a family of totally bounded bitolerance graphs and determines exactly which edge orientations yield a totally bounded bitolerance digraph. It is shown that the classes of totally bounded bitolerance digraphs and interval catch digraphs coincide, implying a polynomial-time recognition algorithm for the former class. In addition, the authors give a counterexample to a 1984 conjecture of H. Maehara.
- A characterization of interval catch digraphs
- A digraph represented by a family of boxes or spheres
- A recognition algorithm for orders of interval dimension two
- Bipartite tolerance orders
- Bounded bitolerance digraphs
- scientific article; zbMATH DE number 3853140 (Why is no real title available?)
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3877239 (Why is no real title available?)
- scientific article; zbMATH DE number 3679885 (Why is no real title available?)
- scientific article; zbMATH DE number 512915 (Why is no real title available?)
- scientific article; zbMATH DE number 1156649 (Why is no real title available?)
- Incidence matrices, interval graphs and seriation in archeology
- Interval digraphs: An analogue of interval graphs
- Matrix and Network Models in Archaeology
- On the Interplay Between Interval Dimension and Dimension
- Proper and unit tolerance graphs
- Semiorders and a Theory of Utility Discrimination
- Tolerance graphs
This page was built for publication: Cliques that are tolerance digraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1382269)
