Tolerance graph

Tolerance graph --- толерантный граф.

A graph [math]\displaystyle{ G = (V,E) }[/math] is a tolerance graph (an interval tolerance graph), if there exists a finite collection [math]\displaystyle{ I = \{I_{x}: x \in V\} }[/math] of closed intervals on a line and a set [math]\displaystyle{ t = \{t_{x}: x \in V\} }[/math] of positive numbers satisfying [math]\displaystyle{ (x,y) \in E }[/math] iff [math]\displaystyle{ |I_{x} \cap I_{y}| \geq \min \{t_{x}, t_{y}\} }[/math] (where [math]\displaystyle{ |I| }[/math] denotes the length of [math]\displaystyle{ I }[/math]).

The pair [math]\displaystyle{ (I,t) }[/math] is called a tolerance representation of [math]\displaystyle{ G }[/math]. A tolerance representation [math]\displaystyle{ (I,t) }[/math] is bounded if [math]\displaystyle{ t_{x} \geq |I_{x}| }[/math] for all [math]\displaystyle{ x \in V }[/math]. [math]\displaystyle{ G }[/math] is a bounded tolerance graph, if [math]\displaystyle{ G }[/math] is a tolerance graph which admits a bounded tolerance representation.

The class of tolerance graph is the subclass of weakly chordal graphs.