𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Subdivisions in Planar Graphs

✍ Scribed by Xingxing Yu

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
741 KB
Volume
72
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

Given four distinct vertices in a 4-connected planar graph G, we characterize when the graph G contains a K 4 -subdivision with the given vertices as its degree three vertices. This result implies the following conjecture of Robertson and Thomas: a 5-connected planar graph has no K 4 -subdivision with specified degree three vertices, if and only if the four specified vertices are contained in a facial cycle in the unique plane embedding of the graph.

πŸ“œ SIMILAR VOLUMES

Subdivisions, parity and well-covered gr
Subdivisions, parity and well-covered graphs
✍ Caro, Yair πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 121 KB πŸ‘ 2 views

A graph is well-covered if every maximal independent set is maximum. This concept, introduced by Plummer in 1970 (J. Combin. Theory 8 (1970)), is the focal point of much interest and current research. We consider well-covered 2-degenerate graphs and supply a structural (and polynomial time algorithm

Some probabilistic and extremal results
Some probabilistic and extremal results on subdivisions and odd subdivisions of graphs
✍ Leif KjΓ¦r JΓΈrgensen πŸ“‚ Article πŸ“… 1989 πŸ› John Wiley and Sons 🌐 English βš– 514 KB

A probabilistic result of Bollobas and Catlin concerning the largest integer p so that a subdivision of K, is contained in a random graph is generalized to a result concerning the largest integer p so that a subdivision of A, is contained in a random graph for some sequence Al, A\*, . . . of graphs