Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Characterizing Path Graphs by Forbidden Induced Subgraphs
 
research article

Characterizing Path Graphs by Forbidden Induced Subgraphs

Leveque, Benjamin
•
Maffray, Frederic
•
Preissmann, Myriam
2009
Journal Of Graph Theory

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
  • Metrics
Type
research article
DOI
10.1002/jgt.20407
Web of Science ID

WOS:000271918800006

Author(s)
Leveque, Benjamin
Maffray, Frederic
Preissmann, Myriam
Date Issued

2009

Published in
Journal Of Graph Theory
Volume

62

Start page

369

End page

384

Subjects

intersection graphs

•

path graphs

•

forbidden induced subgraphs

•

Intersection Graphs

•

Interval-Graphs

•

Recognition

•

Algorithms

•

Tree

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
ROSE  
Available on Infoscience
November 30, 2010
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/59606
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés