UNIT AND PROPER BITOLERANCE DIGRAPHS

In this paper we prove that the following statements about a directed graph (G) over right arrow are equivalent. (1) (G) over right arrow is a unit bitolerance digraph, (2) (G) over right arrow is a proper bito lerance digraph, and (3) the digraph obtained by reversing all are dir ections of (G) over right arrow is an interval catch digraph (also kno wn as a point-core digraph). This result combined with known algorithm s for recognizing interval catch digraphs, gives the first known polyn omial-time algorithm for recognizing a class of (bi)tolerance digraphs . (C) 1997 John Wiley & Sons. Inc.