Cliques that are tolerance digraphs (Q1382269)

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.