๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Traceability in graphs with forbidden triples of subgraphs

โœ Scribed by Ronald J. Gould; John M. Harris

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
724 KB
Volume
189
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

โœฆ Synopsis

If 9 is a collection of connected graphs, and if a graph G does not contain any member of 9 as an induced subgraph, then G is said to be F-free. The members of f in this situation are called forbidden subgraphs. In a previous paper (Gould and Harris, 1995) the authors demonstrated two families of triples of subgraphs which imply traceability when forbidden.

๐Ÿ“œ SIMILAR VOLUMES

Dominating subgraphs in graphs with some
Dominating subgraphs in graphs with some forbidden structures
โœ Jiping Liu; Huishan Zhou ๐Ÿ“‚ Article ๐Ÿ“… 1994 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 387 KB

We characterize the triangle-free graphs with neither induced path of six vertices nor induced cycle of six vertices and the triangle-free graphs without induced path of six vertices in terms of dominating subgraphs.

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