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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [10 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01348863
Contributor : Isabelle Gouat <>
Submitted on : Tuesday, July 26, 2016 - 8:11:57 AM
Last modification on : Friday, August 10, 2018 - 2:12:03 PM
Long-term archiving on : Thursday, October 27, 2016 - 10:31:46 AM

File

[Discussiones Mathematicae Gra...
Publisher files allowed on an open archive

Identifiers

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⟩

Share

Metrics

Record views

141

Files downloads

279