Proper and unit tolerance graphs (Q1894354): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Q1104213 / rank | |||
Property / author | |||
Property / author: Peter C. Fishburn / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3328583 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3322150 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Tolerance graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4029976 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4873748 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: General results on tolerance intersection graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Stability number and chromatic number of tolerance graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5588432 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Revision as of 15:50, 23 May 2024
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