We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

On the intersection of tolerance and cocomparability graphs.

Mertzios, G.B. and Zaks, S. (2010) 'On the intersection of tolerance and cocomparability graphs.', in Algorithms and Computation, 21st International Symposium, ISAAC 2010, 15-17 December 2010, Jeju Island, Korea ; proceedings Part I. Berlin, Heidelberg: Springer, pp. 230-240. Lecture notes in computer science. (6506).


It has been conjectured by Golumbic and Monma in 1984 that the intersection of tolerance and cocomparability graphs coincides with bounded tolerance graphs. Since cocomparability graphs can be efficiently recognized, a positive answer to this conjecture in the general case would enable us to efficiently distinguish between tolerance and bounded tolerance graphs, although it is NP-complete to recognize each of these classes of graphs separately. The conjecture has been proved under some – rather strong – structural assumptions on the input graph; in particular, it has been proved for complements of trees, and later extended to complements of bipartite graphs, and these are the only known results so far. Furthermore, it is known that the intersection of tolerance and cocomparability graphs is contained in the class of trapezoid graphs. In this article we prove that the above conjecture is true for every graph G, whose tolerance representation satisfies a slight assumption; note here that this assumption concerns only the given tolerance representation R of G, rather than any structural property of G. This assumption on the representation is guaranteed by a wide variety of graph classes; for example, our results immediately imply the correctness of the conjecture for complements of triangle-free graphs (which also implies the above-mentioned correctness for complements of bipartite graphs). Our proofs are algorithmic, in the sense that, given a tolerance representation R of a graph G, we describe an algorithm to transform R into a bounded tolerance representation R  ∗  of G. Furthermore, we conjecture that any minimal tolerance graph G that is not a bounded tolerance graph, has a tolerance representation with exactly one unbounded vertex. Our results imply the non-trivial result that, in order to prove the conjecture of Golumbic and Monma, it suffices to prove our conjecture. In addition, there already exists evidence in the literature that our conjecture is true.

Item Type:Book chapter
Additional Information:Event URL:
Keywords:Tolerance graphs, Cocomparability graphs, 3-dimensional intersection model, Trapezoid graphs, Parallelogram graphs.
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:The final publication is available at Springer via
Date accepted:No date available
Date deposited:06 March 2012
Date of first online publication:December 2010
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar