Characterizing path graphs by forbidden induced subgraphs
Loading...
Date
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
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.