Characterizing path graphs by forbidden induced subgraphs |
| |
| Authors: | Benjamin Lévêque Frédéric Maffray Myriam Preissmann |
| |
| Institution: | 1. Rose, EPFL, Lausanne, Switzerland;2. C.N.R.S., Laboratoire G‐SCOP, Grenoble, France |
| |
| 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. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 369–384, 2009 |
| |
| Keywords: | intersection graphs path graphs forbidden induced subgraphs |
|
|
