Andrzej Proskurowski ; Jan Arne Telle - Classes of graphs with restricted interval models

dmtcs:263 - Discrete Mathematics & Theoretical Computer Science, January 1, 1999, Vol. 3 no. 4 -
Classes of graphs with restricted interval modelsArticle

Authors: Andrzej Proskurowski 1; Jan Arne Telle 2

  • 1 Computer Science Department [Oregon]
  • 2 Department of Informatics [Bergen]

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.

Volume: Vol. 3 no. 4
Published on: January 1, 1999
Imported on: March 26, 2015
Keywords: Interval graphs,Pathwidth,Bandwidth,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

2 Documents citing this article

Consultation statistics

This page has been seen 344 times.
This article's PDF has been downloaded 415 times.