Premium
Characterizing path graphs by forbidden induced subgraphs
Author(s) -
Lévêque Benjamin,
Maffray Frédéric,
Preissmann Myriam
Publication year - 2009
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20407
Subject(s) - combinatorics , block graph , mathematics , cograph , discrete mathematics , split graph , path (computing) , chordal graph , longest path problem , graph , 1 planar graph , computer science , programming language
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. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 369–384, 2009