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


Published in:
Journal Of Graph Theory, 62, 369-384
Year:
2009
Keywords:
Laboratories:




 Record created 2010-11-30, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)