Characterizing Path Graphs by Forbidden Induced Subgraphs

A path graph is the intersection graph of subpaths of a tree. In 1970, Renz asked for a characterization of path graphs by forbidden induced subgraphs. We answer this question by determining the complete list of graphs that are not path graphs and are minimal with this property. (C) 2009 Wiley Periodicals, Inc. J Graph Theory 62: 369-384, 2009