Tolerance graph

In graph theory, a tolerance graph is an undirected graph in which every vertex can be represented by a closed interval and a real number called its tolerance, in such a way that two vertices are adjacent in the graph whenever their intervals overlap in a length that is at least the minimum of their two tolerances.^[1] This class of graphs was introduced in 1982 by Martin Charles Golumbic and Clyde Monma, who used them to model scheduling problems in which the tasks to be modeled can share resources for limited amounts of time.^[2]

Every interval graph is a tolerance graph.^[3] The complement graph of every tolerance graph is a perfectly orderable graph, from which it follows that the tolerance graphs themselves are perfect graphs.^[4]

It is NP-complete to determine whether a given graph is a tolerance graph.^[5] However, because tolerance graphs are perfect graphs, many algorithmic problems that are hard on other classes of graphs, including graph coloring and the clique problem, can be solved in polynomial time on tolerance graphs.^[3]

References

^ Golumbic, Martin Charles; Trenk, Ann N. (2004), Tolerance graphs, Cambridge Studies in Advanced Mathematics, vol. 89, Cambridge University Press, doi:10.1017/CBO9780511542985, ISBN 0-521-82758-2, MR 2051713
^ Golumbic, Martin C.; Monma, Clyde L. (1982), "A generalization of interval graphs with tolerances", Proceedings of the thirteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1982), Congressus Numerantium, 35: 321–331, MR 0725892
^ ^a ^b "Graphclass: tolerance", Information System on Graph Classes and their Inclusions, retrieved 2019-09-30
^ Golumbic, Martin Charles; Monma, Clyde L.; Trotter, William T. Jr. (1984), "Tolerance graphs", Discrete Applied Mathematics, 9 (2): 157–170, doi:10.1016/0166-218X(84)90016-7, MR 0761599
^ Mertzios, George B.; Sau, Ignasi; Zaks, Shmuel (2011), "The recognition of tolerance and bounded tolerance graphs" (PDF), SIAM Journal on Computing, 40 (5): 1234–1257, doi:10.1137/090780328, MR 2854571

[gt-1] Golumbic, Martin Charles; Trenk, Ann N. (2004), Tolerance graphs, Cambridge Studies in Advanced Mathematics, vol. 89, Cambridge University Press, doi:10.1017/CBO9780511542985, ISBN 0-521-82758-2, MR 2051713

[gm-2] Golumbic, Martin C.; Monma, Clyde L. (1982), "A generalization of interval graphs with tolerances", Proceedings of the thirteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1982), Congressus Numerantium, 35: 321–331, MR 0725892

[gc-3] "Graphclass: tolerance", Information System on Graph Classes and their Inclusions, retrieved 2019-09-30

[gmt-4] Golumbic, Martin Charles; Monma, Clyde L.; Trotter, William T. Jr. (1984), "Tolerance graphs", Discrete Applied Mathematics, 9 (2): 157–170, doi:10.1016/0166-218X(84)90016-7, MR 0761599

[msz-5] Mertzios, George B.; Sau, Ignasi; Zaks, Shmuel (2011), "The recognition of tolerance and bounded tolerance graphs" (PDF), SIAM Journal on Computing, 40 (5): 1234–1257, doi:10.1137/090780328, MR 2854571

[1]

[2]

[3]

[4]

[5]