Geodesic
Asteroidal Quadruples in non Rooted Path Graphs
Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 4, pp. 603-614

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: clique trees, rooted path graphs, asteroidal quadruples 
@article{DMGT_2015_35_4_a0,
     author = {Gutierrez, Marisa and L\'ev\^eque, Benjamin and Tondato, Silvia B.},
     title = {Asteroidal {Quadruples} in non {Rooted} {Path} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {603--614},
     publisher = {mathdoc},
     volume = {35},
     number = {4},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a0/}
}
TY  - JOUR
AU  - Gutierrez, Marisa
AU  - Lévêque, Benjamin
AU  - Tondato, Silvia B.
TI  - Asteroidal Quadruples in non Rooted Path Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2015
SP  - 603
EP  - 614
VL  - 35
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a0/
LA  - en
ID  - DMGT_2015_35_4_a0
ER  - 
%0 Journal Article
%A Gutierrez, Marisa
%A Lévêque, Benjamin
%A Tondato, Silvia B.
%T Asteroidal Quadruples in non Rooted Path Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2015
%P 603-614
%V 35
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a0/
%G en
%F DMGT_2015_35_4_a0
Gutierrez, Marisa; Lévêque, Benjamin; Tondato, Silvia B. Asteroidal Quadruples in non Rooted Path Graphs. Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 4, pp. 603-614. http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a0/