𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On minimal forbidden subgraph characterizations of balanced graphs

✍ Scribed by Bonomo, Flavia; Durán, Guillermo; Safe, Martín D.; Wagler, Annegret K.

Book ID
122509044
Publisher
Elsevier Science
Year
2013
Tongue
English
Weight
624 KB
Volume
161
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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