Fuzzy Tolerance Graphs

Golumbic and Trenk first introduced tolerance graph [7] to generalize some well-known applications of interval graphs. In a tolerance graph, every vertex is represented by an interval and a tolerance such that an edge occurs if and only if the overlap of corresponding intervals is at least as large as the tolerance associated with one of the vertices. Resource allocation sharing tolerate among users and certain scheduling problems can be modeled by tolerance graphs.