graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, a tolerance graph is an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

in which every vertex can be represented by a

closed interval In mathematics, a (real) interval is a set of real numbers that contains all real numbers lying between any two numbers of the set. For example, the set of numbers satisfying is an interval which contains , , and all numbers in between. Othe ...

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. This class of graphs was introduced in 1982 by

Martin Charles Golumbic Martin Charles Golumbic (born 1948) is a mathematician and computer scientist known for his research on perfect graphs, graph sandwich problems, compiler optimization, and spatial-temporal reasoning. He is a professor emeritus of computer scienc ...

and Clyde Monma, who used them to model

scheduling A schedule or a timetable, as a basic time-management tool, consists of a list of times at which possible tasks, events, or actions are intended to take place, or of a sequence of events in the chronological order in which such things are i ...

problems in which the tasks to be modeled can share resources for limited amounts of time. Every

interval graph In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line, with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals. ...

is a tolerance graph. The

complement graph In the mathematical field of graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in . That is, to generate the complement ...

of every tolerance graph is a

perfectly orderable graph In graph theory, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with that ordering optimally colors every induced subgraph of the given graph. Perfectly orderable graphs form a sp ...

, from which it follows that the tolerance graphs themselves are

perfect graph In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph ( clique number). Equivalently stated in symbolic terms an arbitrary graph G=(V,E) is per ...

s. It is

NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...

to determine whether a given graph is a tolerance graph. However, because tolerance graphs are perfect graphs, many algorithmic problems that are hard on other classes of graphs, including

graph coloring In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices ...

and the

clique problem In computer science, the clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph. It has several different formulations depending on which cliq ...

, can be solved in

polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

on tolerance graphs.

References

{{reflist, refs= {{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 {{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 {{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 {{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 {{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 Perfect graphs