Subdivisions in planar graphs (Q1366603)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Subdivisions in planar graphs |
scientific article |
Statements
Subdivisions in planar graphs (English)
0 references
15 September 1997
0 references
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.
0 references
disjoint paths
0 references
subdivisions
0 references
connectivity
0 references
planar graph
0 references
plane embedding
0 references
