Atlas home ||
Conferences |
Abstracts |
about Atlas
Interval Filament Graphs are Caterpillar Overlap Graphs
by
Jessica Enright
University of Alberta
Coauthors: Lorna Stewart
Intersection and overlap representations of graphs have recently garnered extensive study.
Filament graphs are a generalization of some classes of intersection graph first proposed by Gavril.
We consider three classes of graphs:
- COGs - the overlap graphs of subcaterpillars in a caterpillar
- IFGs - the intersection graphs of interval filaments in a line
- c-SOGs - the overlap graphs of subtrees in a tree with an overlap representation in which a path in the tree intersects all representing subtrees
We show that these three classes are equivalent.
The equivalence of the first two classes was proved independently by the authors of this
work and by Chalopin, Goncalves, and Ochem, who presented their work at the
6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications.
Date received: April 14, 2008
Copyright © 2008 by the author(s).
The author(s) of this document and the organizers of the conference
have granted their consent to include this abstract in
Atlas Conferences Inc.
Document # cauz-15.