Classes of graphs with restricted interval models

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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 1999, 3 (4), pp.167-176
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00958935
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 13 mars 2014 - 16:47:59
Dernière modification le : mercredi 29 novembre 2017 - 10:26:24
Document(s) archivé(s) le : vendredi 13 juin 2014 - 12:01:17

Fichier

dm030404.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00958935, version 1

Collections

Citation

Andrzej Proskurowski, Jan Arne Telle. Classes of graphs with restricted interval models. Discrete Mathematics and Theoretical Computer Science, DMTCS, 1999, 3 (4), pp.167-176. 〈hal-00958935〉

Partager

Métriques

Consultations de la notice

57

Téléchargements de fichiers

156