Asteroidal quadruples in non rooted path graphs

Abstract : A directed path graph is the intersection graph of a family of directed subpaths of a directed tree. A rooted path graph is the intersection graph of a family of directed subpaths of a rooted tree. Rooted path graphs are directed path graphs. Several characterizations are known for directed path graphs: one by forbidden induced subgraphs and one by forbidden asteroids. It is an open problem to find such characterizations for rooted path graphs. For this purpose, we are studying in this paper directed path graphs that are non rooted path graphs. We prove that such graphs always contain an asteroidal quadruple.
Type de document :
Article dans une revue
Discussiones Mathematicae Graph Theory, University of Zielona Góra, 2015, 35 (4), pp.603-614. 〈10.7151/dmgt.1821〉
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01348863
Contributeur : Isabelle Gouat <>
Soumis le : mardi 26 juillet 2016 - 08:11:57
Dernière modification le : vendredi 10 août 2018 - 14:12:03
Document(s) archivé(s) le : jeudi 27 octobre 2016 - 10:31:46

Fichier

[Discussiones Mathematicae Gra...
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

Citation

Marisa Gutierrez, Benjamin Lévêque, Silvia B. Tondato. Asteroidal quadruples in non rooted path graphs. Discussiones Mathematicae Graph Theory, University of Zielona Góra, 2015, 35 (4), pp.603-614. 〈10.7151/dmgt.1821〉. 〈lirmm-01348863〉

Partager

Métriques

Consultations de la notice

86

Téléchargements de fichiers

114