Loading...
research article
Characterizing Path Graphs by Forbidden Induced Subgraphs
Leveque, Benjamin
•
Maffray, Frederic
•
Preissmann, Myriam
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
Type
research article
Web of Science ID
WOS:000271918800006
Authors
Leveque, Benjamin
•
Maffray, Frederic
•
Preissmann, Myriam
Publication date
2009
Published in
Volume
62
Start page
369
End page
384
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
November 30, 2010
Use this identifier to reference this record