Asteroidal quadruples in non rooted path graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue Discussiones Mathematicae Graph Theory Année : 2015

Asteroidal quadruples in non rooted path graphs

Résumé

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.
Fichier principal
Vignette du fichier
[Discussiones Mathematicae Graph Theory] Asteroidal Quadruples in non Rooted Path Graphs.pdf (188.78 Ko) Télécharger le fichier
Origine Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

lirmm-01348863 , version 1 (26-07-2016)

Identifiants

Citer

Marisa Gutierrez, Benjamin Lévêque, Silvia B. Tondato. Asteroidal quadruples in non rooted path graphs. Discussiones Mathematicae Graph Theory, 2015, 35 (4), pp.603-614. ⟨10.7151/dmgt.1821⟩. ⟨lirmm-01348863⟩
100 Consultations
262 Téléchargements

Altmetric

Partager

More