Linking four vertices in graphs of large connectivity
Linking four vertices in graphs of large connectivity
复制标题
连接大连通图中的四个顶点
DOI：
10.1016/j.jctb.2021.12.007
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Koyo Hayashi
中科院分区：
文献类型：
--
作者：
常松祐介;常松祐介;入倉友紀;入倉友紀;入倉友紀;Koyo Hayashi
结构图论最基本的结果之一是“双路径定理”，它通过平面性来表征 2-连接。作为定理的扩展，对于具有四个顶点的固定图 H，我们考虑以下问题：给定图 G 和从 V (H) 到 V (G) 的单射映射，G 中是否存在具有映射指定的四个分支顶点的 H 的细分？因此，情况 H= 2 K 2 对应于 2-连锁问题。在本文中，对于任何具有四个顶点的固定 H，我们给出了没有 H 细分的 6 连通图 G 的结构表征。作为推论，我们证明每个 7 连通图都包含具有指定分支顶点的 K 4 细分。这概括了 McCarty、Wang 和 Yu 的结果，即每个 7 连通图都是 4 序的。我们还证明每个无三角形 6 连通图都包含具有指定分支顶点的 K 4 的细分。这解决了Mader猜想的一个特例。
One of the most fundamental results in structural graph theory is the “two-paths theorem” that characterizes 2-linkage by planarity. As an extension of the theorem, we consider the following problem for a fixed graph H with four vertices: Given a graph G and an injective map from V (H) to V (G), is there a subdivision of H in G with four branch vertices specified by the map? Hence the case H= 2 K 2 corresponds to the 2-linkage problem. In this paper, for any fixed H with four vertices, we give a structural characterization of 6-connected graphs G with no such subdivision of H. As a corollary, we prove that every 7-connected graph contains a subdivision of K 4 with prescribed branch vertices. This generalizes a result of McCarty, Wang and Yu which states that every 7-connected graph is 4-ordered. We also prove that every triangle-free 6-connected graph contains a subdivision of K 4 with prescribed branch vertices. This solves a special case of a conjecture of Mader.