Characterizing path graphs by forbidden induced subgraphs
Benjamin Lévêque, Frédéric Maffray, Myriam Preissmann · arXiv (Cornell University) · 2008
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.