Characterizing Path Graphs by Forbidden Induced Subgraphs
2009
Résumé
A path graph is the intersection graph of subpaths of a tree. In 1970, Renz asked for a characterization of path graphs by forbidden induced subgraphs. We answer this question by determining the complete list of graphs that are not path graphs and are minimal with this property. (C) 2009 Wiley Periodicals, Inc. J Graph Theory 62: 369-384, 2009
Détails
Titre
Characterizing Path Graphs by Forbidden Induced Subgraphs
Auteur(s)
Leveque, Benjamin ; Maffray, Frederic ; Preissmann, Myriam
Publié dans
Journal Of Graph Theory
Volume
62
Pages
369-384
Date
2009
Mots-clés (libres)
Autres identifiant(s)
Afficher la publication dans Web of Science
Laboratoires
ROSE
Le document apparaît dans
Production scientifique et compétences > SB - Faculté des sciences de base > SB Archives > ROSE - Chaire de recherche opérationnelle SE
Production scientifique et compétences > SB - Faculté des sciences de base > Mathématiques
Publications validées par des pairs
Travail produit à l'EPFL
Articles de journaux
Publié
Production scientifique et compétences > SB - Faculté des sciences de base > Mathématiques
Publications validées par des pairs
Travail produit à l'EPFL
Articles de journaux
Publié
Date de création de la notice
2010-11-30