Characterizing Path Graphs by Forbidden Induced Subgraphs
2009
Abstract
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
Details
Title
Characterizing Path Graphs by Forbidden Induced Subgraphs
Author(s)
Leveque, Benjamin ; Maffray, Frederic ; Preissmann, Myriam
Published in
Journal Of Graph Theory
Volume
62
Pages
369-384
Date
2009
Keywords
Other identifier(s)
View record in Web of Science
Laboratories
ROSE
Record Appears in
Scientific production and competences > SB - School of Basic Sciences > SB Archives > ROSE - Chair of Operations Research SE
Scientific production and competences > SB - School of Basic Sciences > Mathematics
Peer-reviewed publications
Work produced at EPFL
Journal Articles
Published
Scientific production and competences > SB - School of Basic Sciences > Mathematics
Peer-reviewed publications
Work produced at EPFL
Journal Articles
Published
Record creation date
2010-11-30