Speaker:
Robert E. Jamison, Professor of Mathematical Sciences,
Clemson University
Title:
Rank Tolerance Graph Classes
Time and location: 12:30 pm - 2 pm, CoRE A, Room 301,
Rutgers University.
Lunch will be served.
Abstract
The objects of study in this talk arise from a natural
extension of ideas that have grown out of the now
classical notion of interval graph. In an interval
graph, each vertex is associated with an interval on the
real line with two vertices adjacent if and only if their
associated intervals intersect. In 1982 Golumbic and others
suggested associating "tolerances" with each interval so that
now two vertices are joined iff the length of the intersection
of their associated intervals is at least the minimum
of the two tolerances. In 1987 McMorris and others
proposed replacing the min function above by other
joint tolerance functions,
such as max or sum an arbitrary function phi.
In the investigation of phi-tolerance interval graphs, a
particular case appeared to be of recurring interest -
namely, when all the intervals are nested to form a chain
under inclusion. In this case, the length of the intersection
is just the minimum of the two lengths,
and only the lengths, and not the actual intervals play a
role in determining adjacency. One can thus think of a
phi-tolerance chain interval graph as arising from the
assignment of two numbers tv and rv
to each vertex v of the graph. The first of these, tv,
is just a tolerance at the vertex v as before.
The second, rv, represents a rank (or size) associated with
the vertex v. Then two vertices v and w are adjacent
provided the minimum of their two ranks exceeds their joint
tolerance - that is,