# Tolerance graph

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Tolerance_graph
> Markdown URL: https://mediated.wiki/source/Tolerance_graph.md
> Source: https://en.wikipedia.org/wiki/Tolerance_graph
> Source revision: 1329691591
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [graph theory](/source/graph_theory), a '''tolerance graph''' is an [undirected graph](/source/undirected_graph) in which every vertex can be represented by a [closed interval](/source/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.{{r|gt}}
This class of graphs was introduced in 1982 by [Martin Charles Golumbic](/source/Martin_Charles_Golumbic) and Clyde Monma, who used them to model [scheduling](/source/Scheduling_(production_processes)) problems in which the tasks to be modeled can share resources for limited amounts of time.{{r|gm}}

Every [interval graph](/source/interval_graph) is a tolerance graph.{{r|gc}} The [complement graph](/source/complement_graph) of every tolerance graph is a [perfectly orderable graph](/source/perfectly_orderable_graph), from which it follows that the tolerance graphs themselves are [perfect graph](/source/perfect_graph)s.{{r|gmt}}

It is [NP-complete](/source/NP-complete) to determine whether a given graph is a tolerance graph.{{r|msz}}
However, because tolerance graphs are perfect graphs, many algorithmic problems that are hard on other classes of graphs, including [graph coloring](/source/graph_coloring) and the [clique problem](/source/clique_problem), can be solved in [polynomial time](/source/polynomial_time) on tolerance graphs.{{r|gc}}

==References==
<references>

<ref name=gc>{{citation|url=http://www.graphclasses.org/classes/gc_169.html|title=Graphclass: tolerance|work=Information System on Graph Classes and their Inclusions|accessdate=2019-09-30}}</ref>

<ref name=gm>{{citation
 | last1 = Golumbic | first1 = Martin C. | author1-link = Martin Charles Golumbic
 | last2 = Monma | first2 = Clyde L.
 | department = Proceedings of the thirteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1982)
 | journal = Congressus Numerantium
 | mr = 725892
 | pages = 321–331
 | title = A generalization of interval graphs with tolerances
 | volume = 35
 | year = 1982}}</ref>

<ref name=gmt>{{citation
 | last1 = Golumbic | first1 = Martin Charles | author1-link = Martin Charles Golumbic
 | last2 = Monma | first2 = Clyde L.
 | last3 = Trotter | first3 = William T. Jr. | author3-link = William T. Trotter
 | doi = 10.1016/0166-218X(84)90016-7
 | issue = 2
 | journal = Discrete Applied Mathematics
 | mr = 761599
 | pages = 157–170
 | title = Tolerance graphs
 | volume = 9
 | year = 1984| doi-access = free
 }}</ref>

<ref name=gt>{{citation
 | last1 = Golumbic | first1 = Martin Charles | author1-link = Martin Charles Golumbic
 | last2 = Trenk | first2 = Ann N. | author2-link = Ann Trenk
 | doi = 10.1017/CBO9780511542985
 | isbn = 0-521-82758-2
 | mr = 2051713
 | publisher = Cambridge University Press
 | series = Cambridge Studies in Advanced Mathematics
 | title = Tolerance graphs
 | volume = 89
 | year = 2004}}</ref>

<ref name=msz>{{citation
 | last1 = Mertzios | first1 = George B.
 | last2 = Sau | first2 = Ignasi
 | last3 = Zaks | first3 = Shmuel
 | doi = 10.1137/090780328
 | issue = 5
 | journal = SIAM Journal on Computing
 | mr = 2854571
 | pages = 1234–1257
 | title = The recognition of tolerance and bounded tolerance graphs
 | volume = 40
 | year = 2011| url = http://dro.dur.ac.uk/9046/1/9046.pdf
 }}</ref>

</references>

Category:Perfect graphs
Category:NP-complete problems

---
Adapted from the Wikipedia article [Tolerance graph](https://en.wikipedia.org/wiki/Tolerance_graph) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Tolerance_graph?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.