Neighborhood subtree tolerance graphs

AbstractIn this paper, we introduce neighborhood subtree tolerance (NeST) graphs which are defined in terms of the tolerance-intersection of neighborhood subtrees of a tree. This class of graphs extends the class of interval tolerance graphs which are defined in terms of the tolerance-intersection of intervals on the real line. Interval tolerance graphs were first introduced by Golumbic and Monma as tolerance graphs. Some relationships among interval tolerance, NeST, and weakly triangulated graphs are examined. The main result shows that NeST graphs are weakly triangulated graphs. In addition, proper NeST graphs are shown to be exactly bounded NeST graphs and NeST graphs with constant tolerance are shown to be strongly chordal