Cliques that are tolerance digraphs (Q1382269)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Cliques that are tolerance digraphs |
scientific article; zbMATH DE number 1133165
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Cliques that are tolerance digraphs |
scientific article; zbMATH DE number 1133165 |
Statements
Cliques that are tolerance digraphs (English)
0 references
14 September 1998
0 references
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.
0 references
tolerance digraphs
0 references
clique
0 references
bitolerance digraphs
0 references
recognition algorithm
0 references
