Is there any real application of Max-Tolerance Graphs, Interval Graphs? I have read one article about Max-Tolerance Graph:.
Basically: Max-tolerance graphs can be regarded as generalized interval graphs, where two intervals $I_i$ and $I_j$ induce an edge in the corresponding graph iff they overlap for an amount of at least $max$ {$t_i$ , $t_j$} where $t_i$ is an individual tolerance parameter associated to each interval $I_i$
Reference
But what is the real application of it and of Interval Graphs $IG$ as well ?
 A: Interval graphs have many applications, I will describe two.
The fist application is for scheduling tasks that have a given start and end date (taxi rides, construction, etc.). Two tasks that overlap cannot be done simultaneously by the same person. How do you minimize the number of people in order for each task to be done ? You can model this with an interval graph, each task's interval is a vertex, and two vertices are linked by an edge if their corresponding interval overlap. Then, minimizing the number of people to accomplish the tasks if equivalent to finding the chromatic number of the graph, which is easy on such graphs (greedy algorithms achieve this).
The second application is rather amusing. It was made up by Claude Berge and many have developed the idea. With interval graphs, you can solve police investigations. Claude Berge's idea was as follows. Imagine a document has been stolen in a building, and the police knows exactly who has been in and out of the building. The detective asks everyone who he has seen in the building, and builds the corresponding graph: a vertex per person, and an edge between two vertices if they were together in the building at some point. It is clear that this graph should be an interval graph. But if someone is lying, the graph will not be an interval graph. Berge then solves the problem by showing that the graph is an interval graph if and only if one or a few edges are removed, and deduces the guilty person.
