Cookies

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. (2016) 'On the intersection of tolerance and cocomparability graphs.', Discrete applied mathematics., 199 . pp. 46-88.

Abstract

Tolerance graphs have been extensively studied since their introduction, due to their interesting structure and their numerous applications, as they generalize both interval and permutation graphs in a natural way. It has been conjectured by Golumbic, Monma, and Trotter 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. This longstanding 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. Our main result in this article is that the above conjecture is true for every graph G that admits a tolerance representation with exactly one unbounded vertex; note that this assumption concerns only the given tolerance representation R of G, rather than any structural property of G. Moreover, our results imply as a corollary that the conjecture of Golumbic, Monma, and Trotter is true for every graph G = (V,E) that has no three independent vertices a, b, c ∈ V such that N(a) ⊂ N(b) ⊂ N(c), where N(v) denotes the set of neighbors of a vertex v ∈ V ; this is satisfied in particular when G is the complement of a triangle-free graph (which also implies the above-mentioned correctness for complements of bipartite graphs). Our proofs are constructive, in the sense that, given a tolerance representation R of a graph G, we 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, Monma, and Trotter, it suffices to prove our conjecture.

Item Type:Article
Keywords:Tolerance graphs, Cocomparability graphs, 3-dimensional intersection model, Trapezoid graphs, Parallelogram graphs.
Full text:(AM) Accepted Manuscript
Download PDF
(863Kb)
Full text:(NA) Not Applicable
Available under License - Creative Commons Attribution.
Download PDF (Corrected proof)
(943Kb)
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution.
Download PDF
(986Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1016/j.dam.2014.10.025
Publisher statement:© 2014 Durham University. Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/3.0/).
Date accepted:27 October 2014
Date deposited:06 November 2014
Date of first online publication:13 November 2014
Date first made open access:No date available

Save or Share this output

Export:
Export
Look up in GoogleScholar