Classes of graphs with restricted interval models - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 1999

Classes of graphs with restricted interval models

Résumé

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.
Fichier principal
Vignette du fichier
dm030404.pdf (123.08 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00958935 , version 1 (13-03-2014)

Identifiants

Citer

Andrzej Proskurowski, Jan Arne Telle. Classes of graphs with restricted interval models. Discrete Mathematics and Theoretical Computer Science, 1999, Vol. 3 no. 4 (4), pp.167-176. ⟨10.46298/dmtcs.263⟩. ⟨hal-00958935⟩

Collections

TDS-MACS
32 Consultations
879 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More