Bounded bitolerance digraphs Original Research Article

Bounded tolerance graphs were introduced in Golumbic and Monma (Congr. Numer. 35 (1982) 321–331) and Golumbic et al. (Discrete Appl. Math. 9 (1984) 157–170) as a generalization of interval graphs. Several variations of bounded tolerance graphs have been studied, including bounded bitolerance graphs. In this paper, we introduce directed versions of the classes of tolerance graphs. We characterize the class of bounded bitolerance digraphs in terms of interval orders. In addition, we characterize those bounded bitolerance digraphs which arise when linear orders or weak orders are used in place of interval orders.