A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three
A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three
复制标题
用于排除没有三阶边切割的图中的浸没的全局分解定理
DOI：
10.1016/j.jctb.2022.01.005
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Liu, Chun-Hung
中科院分区：
文献类型：
--
作者：
Liu, Chun-Hung
一个图G包含另一个图H作为浸入，如果H可以从G的一个子图通过分裂边和去除孤立点而得到。浸入包含有一个明显的必要度条件：如果G包含H作为浸入，则对任意整数k，G中至少k次顶点的个数至少等于H中至少k次顶点的个数。本文证明了这一明显的必要条件对于无3阶边割的图是“几乎”充分的：对于任意图H，任意无3阶边割的H-浸入图都可以由图的边和得到，其中每个和都是由一个违反明显度条件的图通过增加有界边数得到的.没有3阶边割的条件是必要的。这个定理的一个简单应用是：对于每个最大度d≥ 4的图H，存在一个整数c，使得对于每个正整数m，最多有c m个无孤立点的未标号d-边连通H-浸入自由m-边图，同时存在超指数多个无孤立点的未标号（d-1）-边连通H-浸入自由m-边图.我们的结构定理将应用于即将发表的关于确定H-浸入自由图类的簇色数的论文中。
A graph G contains another graph H as an immersion if H can be obtained from a subgraph of G by splitting off edges and removing isolated vertices. There is an obvious necessary degree condition for the immersion containment: if G contains H as an immersion, then for every integer k, the number of vertices of degree at least k in G is at least the number of vertices of degree at least k in H. In this paper, we prove that this obvious necessary condition is “nearly” sufficient for graphs with no edge-cut of order 3: for every graph H, every H-immersion free graph with no edge-cut of order 3 can be obtained by an edge-sum of graphs, where each of the summands is obtained from a graph violating the obvious degree condition by adding a bounded number of edges. The condition for having no edge-cut of order 3 is necessary. A simple application of this theorem shows that for every graph H of maximum degree d≥ 4, there exists an integer c such that for every positive integer m, there are at most c m unlabeled d-edge-connected H-immersion free m-edge graphs with no isolated vertex, while there are superexponentially many unlabeled (d− 1)-edge-connected H-immersion free m-edge graphs with no isolated vertex. Our structure theorem will be applied in a forthcoming paper about determining the clustered chromatic number of the class of H-immersion free graphs.
登录
查看更多内容
DOI：
--
发表时间：
2016
期刊：
Electron. Notes Discret. Math.
影响因子：
--
作者：
Tien;Paul Wollan
通讯作者：
Paul Wollan
DOI：
--
发表时间：
2003
期刊：
J. Comb. Theory B
影响因子：
--
作者：
N. Robertson;P. Seymour
通讯作者：
P. Seymour
DOI：
--
发表时间：
2012
期刊：
arXiv.org
影响因子：
--
作者：
Zdenek Dvorák
通讯作者：
Zdenek Dvorák
影响因子：
1.4
作者：
Wollan, Paul
通讯作者：
Wollan, Paul
缠结树对偶性：在图、拟阵及其他领域
影响因子：
1.1
作者：
R. Diestel;Sang
通讯作者：
Sang