Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903847 | Journal of Combinatorial Theory, Series B | 2018 | 30 Pages |
Abstract
A graph G is weakly 4-connected if it is 3-connected, has at least five vertices, and for every pair (A,B) such that AâªB=V(G), |Aâ©B|=3 and no edge has one end in AâB and the other in BâA, one of the induced subgraphs G[A],G[B] has at most four edges. We describe a set of constructions that starting from a weakly 4-connected planar graph G produce a finite list of non-planar weakly 4-connected graphs, each having a minor isomorphic to G, such that every non-planar weakly 4-connected graph H that has a minor isomorphic to G has a minor isomorphic to one of the graphs in the list. Our main result is more general and applies in particular to polyhedral embeddings in any surface.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Rajneesh Hegde, Robin Thomas,