𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Forbidden induced subgraphs for star-free graphs

✍ Scribed by Jun Fujisawa; Katsuhiro Ota; Kenta Ozeki; Gabriel Sueiro

Book ID
113567391
Publisher
Elsevier Science
Year
2011
Tongue
English
Weight
291 KB
Volume
311
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Line Graphs and Forbidden Induced Subgra
Line Graphs and Forbidden Induced Subgraphs
✍ Hong-Jian Lai; Δ½ubomΔ±́r Ε oltΓ©s πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 242 KB

Beineke and Robertson independently characterized line graphs in terms of nine forbidden induced subgraphs. In 1994, S8 olte s gave another characterization, which reduces the number of forbidden induced subgraphs to seven, with only five exceptional cases. A graph is said to be a dumbbell if it con

Characterizing path graphs by forbidden
Characterizing path graphs by forbidden induced subgraphs
✍ Benjamin LΓ©vΓͺque; FrΓ©dΓ©ric Maffray; Myriam Preissmann πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 197 KB

## 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