RUTCOR Colloquia - February 3, 2005
Speaker: Martin Charles Golumbic
Affiliation: Caesarea Rothschild Institute, University of Haifa, Haifa, Israel
Title: The k-edge intersection graphs of paths in a tree
Time: 1:30 - 2:30 PM
Location: RUTCOR Building - Room 139, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We consider a generalization of edge intersection graphs of paths
in a tree. Let P be a collection of nontrivial simple
paths in a tree T. We define the k-edge (k ³ 1)
intersection graph Gk(P), such that the vertices
correspond to the members of P, and we join two vertices
by an edge if the corresponding members of P share k
edges in T. An undirected graph G is called a k-edge
intersection graph of paths in a tree, and denoted by k-EPT, if
G = Gk(P) for some P and T.
It is known that the recognition of the 1-EPT graphs is NP-complete.
We prove that the recognition of the k-EPT graphs is also NP-complete for
any fixed k ³ 2. We show that the family of 1-EPT graphs is
contained, but not equal, to the family of k-EPT graphs for any
fixed k ³ 2, and that there exists an infinite family of
graphs that are not k-EPT graph for every k ³ 1. We further
investigate the hierarchy of a large number of these graph classes.
The edge intersection graphs are used in network applications.
Scheduling undirected calls in a tree is equivalent to coloring an edge
intersection graph of paths in a tree.
Joint work with Marina Lipshteyn and Michal Stern.
Back to Seminars Page.
Back to RUTCOR homepage.
| 
