Proper and unit tolerance graphs (Q1894354)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Proper and unit tolerance graphs |
scientific article |
Statements
Proper and unit tolerance graphs (English)
0 references
28 January 1996
0 references
A tolerance graph (TG) is a graph in which each vertex can be represented by an interval and a tolerance such that an edge occurs if and only if the overlap of the corresponding intervals is at least as large as the tolerance associated with one of the vertices. If no interval is properly contained in another then the graph is called a proper TG; if all the intervals have the same length then the graph is called a unit TG. The authors answer a question of \textit{M. C. Golumbic}, \textit{C. L. Monma} and \textit{W. T. Trotter} [Tolerance graphs, Discrete Appl. Math. 9, 154-170 (1984; Zbl 0547.05054)]. Also related results are given.
0 references
interval graph
0 references
tolerance graph
0 references