Cliques that are tolerance digraphs

From MaRDI portal





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.











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)