Non-embeddable extensions of embedded minors
Non-embeddable extensions of embedded minors
复制标题
嵌入式未成年人的不可嵌入式扩展
DOI：
10.1016/j.jctb.2018.01.004
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Thomas, Robin
中科院分区：
文献类型：
--
作者：
Hegde, Rajneesh;Thomas, Robin
一个图G是弱4-连通的，如果它是3-连通的，至少有5个顶点，并且对于每个对（A，B），使得A ∈ B= V（G），|A、B、B| = 3且没有边的一端在A-B中，另一端在B-A中，则导出子图G [A]，G [B]中的一个至多有4条边.我们描述了一组构造，从弱4-连通平面图G产生一个有限的非平面弱4-连通图列表，每个图都有一个子同构于G，使得每个非平面弱4-连通图H有一个子同构于G有一个子同构于列表中的一个图。我们的主要结果是更一般的，特别适用于多面体嵌入在任何表面。
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.