𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Minors of quasi 4-connected graphs

✍ Scribed by Themistocles Politof; A. Satyanarayana

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
744 KB
Volume
126
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

A minimal point disconnecting set S of a graph G is a nontrivial m-separator, where m=IS), if the connected components of G-S can be partitioned into two sets each of which has at least two points. A 3-connected graph is quasi 4-connected if it has no nontrivial S-separators. Let G be a quasi 4-connected graph. It is proved that (i) if G is nonplanar with 7 or more points then G is either isomorphic to Cs(1,4) or Ks is a minor of G and (ii) if G is planar with 9 or more points then G is K, x Cs or K, 2 z is a minor of G. Some well-known results follow from this as .

corollaries.

📜 SIMILAR VOLUMES

Unavoidable parallel minors of 4-connect
Unavoidable parallel minors of 4-connected graphs
✍ Carolyn Chun; Guoli Ding; Bogdan Oporowski; Dirk Vertigan 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 154 KB

## Abstract A __parallel minor__ is obtained from a graph by any sequence of edge contractions and parallel edge deletions. We prove that, for any positive integer __k__, every internally 4‐connected graph of sufficiently high order contains a parallel minor isomorphic to a variation of __K__~4,__k

The structure of quasi 4-connected graph
The structure of quasi 4-connected graphs
✍ Themistocles Politof; A. Satyanarayana 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 646 KB

A minimal point disconnecting set S of a graph G is a nontrivial m-separator, where m = IS I, if the connected components of G -S can be partitioned into two subgraphs each of which has at least two points. A 3-connected graph is quasi 4-connected if it has no nontrivial 3separators. This paper prov

Minors in large almost-5-connected non-p
Minors in large almost-5-connected non-planar graphs
✍ Ken-Ichi Kawarabayashi; John Maharry 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 196 KB

## Abstract It is shown that every sufficiently large almost‐5‐connected non‐planar graph contains a minor isomorphic to an arbitrarily large graph from one of six families of graphs. The graphs in these families are also almost‐5‐connected, by which we mean that they are 4‐connected and all 4‐sepa

Connectivity, graph minors, and subgraph
Connectivity, graph minors, and subgraph multiplicity
✍ David Eppstein 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 435 KB

## Abstract It is well known that any planar graph contains at most __O__(__n__) complete subgraphs. We extend this to an exact characterization: __G__ occurs __O__(__n__) times as a subgraph of any planar graph, if and only if __G__ is three‐connected. We generalize these results to similarly char

Uncontractable 4-connected graphs
Uncontractable 4-connected graphs
✍ Nicola Martinov 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 98 KB

## Abstract The only uncontractable 4‐connected graphs are __C__^2^~__n__~ for __n__ ≥ 5 and the line graphs of the cubic cyclically 4‐connected graphs.