Unit and proper bitolerance digraphs
Randy Shull, Ann N. Trenk · Journal of Graph Theory · 1997
In this paper we prove that the following statements about a directed graph G are equivalent. (1) G is a unit bitolerance digraph, (2) G is a proper bitolerance digraph, and (3) the digraph obtained by reversing all arc directions of G is an interval catch digraph (also known as a point-core digraph). This result combined with known algorithms for recognizing interval catch digraphs, gives the first known polynomial-time algorithm for recognizing a class of (bi)tolerance digraphs. © 1997 John Wiley & Sons, Inc.