Tolerance graphs (Q798675)

An undirected graph G with the vertex set V is called a tolerance graph if there exists a collection \(\{I_ x| v\in V\}\) of closed intervals on a line and a set \(\{t_ x| x\in V\}\) of positive numbers such that two vertices x, y of G are adjacent if and only if \(| I_ x\cap I_ y|\geq \min\{t_ x,t_ y\}.\) If \(t_ x\leq| I_ x|\) for all \(x\in V\), a tolerance graph G is called bounded. Various conditions for tolerance graphs are studied. Among other results a theorem is proved stating that every bounded tolerance graph is the complement of a comparability graph (i.e. a graph whose edges can be oriented in such a way that the resulting digraph is transitive). Further conditions concern forbidden subgraphs. The so-called proper tolerance graphs are defined and investigated. At the end applications of tolerance graphs in organization problems in the human society are shown and some open problems are presented.