2 Mathematical background In this section we will define the formal basis and repeat some earlier derived results that are essential for the understanding of the rest of the article. Let S denote a set of n intervals Ii = [xi, yi], 1 ≤ i ≤ n, xi, yi ∈ ℕ, xi c · |Ii|. In a general max-tolerance graph each interval Ii is associated with a tolerance 0 ≤ ti ≤ |Ii| and here, two intervals are said to tolerate each other, if |Ii ⋂ Ij| ≥ max{ti, tj}. Given a graph G = (V, E), a clique is a subset C ⊆ V of pairwise-connected vertices. A clique C is called a maximal clique if there is no other clique C' ⊃ C. A clique is a maximum clique if its cardinality is of largest possible size. The following lemma has been derived for general max-tolerance graphs and applies also to c-max-tolerance graphs [9]: Lemma 1 The number of maximal cliques in (c-)max-tolerance graphs is O(n3). This result has been derived by a fundamental equivalence, for which we will need the following definitions: Let S = {[x1, y1], [x2, y2],..., [xn, yn]} be a set of intervals and let 0