Logo image
Sign in
Characterizing path graphs by forbidden induced subgraphs
Journal article   Open access   Peer reviewed

Characterizing path graphs by forbidden induced subgraphs

Benjamin Lévêque, Frédéric Maffray and Myriam Preissmann
Journal of Graph Theory, Vol.62(4), pp.369-384
2009

Abstract

A graph is a path graph if it is the intersection graph of a family of subpaths of a tree. In 1970, Renz asked for a characterizaton of path graphs by forbidden induced subgraphs. Here we answer this question by listing all graphs that are not path graphs and are minimal with this property.
url
Find in HALView

Metrics

1 Record Views

Details

Logo image