Discrete Mathematics & Theoretical Computer Science
Volume 3 n° 4 (1999), pp. 167-176
| author: | Andrzej Proskurowski and Jan Arne Telle |
|---|---|
| title: | Classes of graphs with restricted interval models |
| keywords: | Interval graphs, Pathwidth, Bandwidth |
| abstract: | We introduce q-proper interval graphs as interval graphs with interval models in which no interval is properly contained in more than q other intervals, and also provide a forbidden induced subgraph characterization of this class of graphs. We initiate a graph-theoretic study of subgraphs of q-proper interval graphs with maximum clique size k+1 and give an equivalent characterization of these graphs by restricted path-decomposition. By allowing the parameter q to vary from 0 to k, we obtain a nested hierarchy of graph families, from graphs of bandwidth at most k to graphs of pathwidth at most k. Allowing both parameters to vary, we have an infinite lattice of graph classes ordered by containment. |
| reference: | Andrzej Proskurowski and Jan Arne Telle (1999), Classes of graphs with restricted interval models, Discrete Mathematics and Theoretical Computer Science 3, pp. 167-176 |
| ps.gz-source: | dm030404.ps.gz (42 K) |
| ps-source: | dm030404.ps (111 K) |
| pdf-source: | dm030404.pdf (89 K) |
The first source gives you the `gzipped' PostScript, the second the plain PostScript and the third the format for the Adobe accrobat reader. Depending on the installation of your web browser, at least one of these should (after some amount of time) pop up a window for you that shows the full article. If this is not the case, you should contact your system administrator to install your browser correctly.
Automatically produced on Mon Nov 15 14:31:40 CET 1999 by novelli