The Structure of the Intersection of Tolerance and Cocomparability Graphs
George B. Mertzios, Shmuel Zaks
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. The conjecture has been proved under some
- rather strong - \emph{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 \emph{representation} $R$ of $G$, rather than \emph{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^{\ast}$ of $G$. Furthermore, we conjecture that any
\emph{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. In addition, there already exists evidence in the literature
that our conjecture is true.