# DIMACS Discrete Mathematics Seminar

## Title:

Unit vs. Proper for Generalizations of Interval Graphs

## Speaker:

- Ann Trenk
- Wellesley College and DIMACS

## Place:

- DIMACS Seminar Room 431, CoRE Building
- Busch Campus, Rutgers University

## Time:

- 4:30 PM
- Tuesday, October 24, 1995

## Abstract:

Interval graphs have been studied extensively both because they have
many applications and because many problems which are NP-complete for
general graphs, admit polynomial-time solutions when restricted to the
class of interval graphs. Formally, a graph G is an interval graph if
it can be represented as follows: each vertex of G corresponds to a
real interval so that two vertices are adjacent in G if and only if
their corresponding intervals intersect.
Unit interval graphs are those which have an interval representation
in which every interval has the same length. Likewise, proper
interval graphs are those which have an interval representation in
which no interval properly contains another. Clearly the class of
unit interval graphs is a subset of the class of proper interval
graphs. In 1969, Fred Roberts showed that these classes are in fact
equal.

We study tolerance and bitolerance graphs which generalize interval
graphs by allowing a certain amount of overlap of intervals before an
edge is formed between the corresponding vertices. We formalize this
notion in the talk and discuss which classes have been characterized,
which have efficient recognition algorithms, and then focus on the
questions of when the unit and proper subclasses are equal.

Document last modified on October 17, 1995