Article ID Journal Published Year Pages File Type
8903847 Journal of Combinatorial Theory, Series B 2018 30 Pages PDF
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.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,