𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Forbidden induced subgraphs for line graphs

✍ Scribed by Ľubomír Šoltés

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
209 KB
Volume
132
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

On planar intersection graphs with forbi
On planar intersection graphs with forbidden subgraphs
✍ János Pach; Micha Sharir 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 154 KB

## Abstract Let ${\cal C}$ be a family of __n__ compact connected sets in the plane, whose intersection graph $G({\cal C})$ has no complete bipartite subgraph with __k__ vertices in each of its classes. Then $G({\cal C})$ has at most __n__ times a polylogarithmic number of edges, where the exponent