Discrete Mathematics & Theoretical Computer Science, Vol 3, No 4 (1999)

Font Size:  Small  Medium  Large

Classes of graphs with restricted interval models

Andrzej Proskurowski, Jan Arne Telle


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.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page