Characterizing path graphs by forbidden induced subgraphs

Simple item page
dc.creatorLévêque, Benjamin
dc.creatorMaffray, Frédéric
dc.creatorPreissmann, Myriam
dc.date2008-03-06
dc.date2008-04-17
dc.date.accessioned2026-07-07T12:17:28Z
dc.date.available2026-07-07T12:17:28Z
dc.descriptionA graph is a path graph if it is the intersection graph of a family of subpaths of a tree. In 1970, Renz asked for a characterizaton of path graphs by forbidden induced subgraphs. Here we answer this question by listing all graphs that are not path graphs and are minimal with this property.
dc.identifierhttps://arxiv.org/abs/0803.0956
dc.identifierhttp://arxiv.org/abs/0803.0956
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/212088
dc.subjectDiscrete Mathematics
dc.titleCharacterizing path graphs by forbidden induced subgraphs
dc.typetext

Files

Collections

arXiv