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