Partitioning H -minor free graphs into three subgraphs with no large components
Partitioning H -minor free graphs into three subgraphs with no large components
复制标题
将 H 小自由图划分为三个没有大分量的子图
DOI：
10.1016/j.jctb.2017.08.003
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Oum, Sang-il
中科院分区：
文献类型：
--
作者：
Liu, Chun-Hung;Oum, Sang-il
证明了：对任意图H，若G没有（奇）H子图，则它的顶点集V（G）可划分为X1，X2，X3，使得对任意i，在Xi上导出的子图没有比H和G的最大度的函数更大的分支.这改进了Alon，Ding，Oporowski和Vertigan（2003）[1]的先前结果，即如果G没有H子式，则V（G）可以划分为四个这样的集合。我们的定理推广了Esperet和Jaret（2014）[9]的结果，他们证明了可嵌入固定曲面上的图，并询问它是否适用于没有H子式的图。作为推论，我们证明了：对任意正整数t，如果图G没有Kt + 1子图，则它的顶点集V（G）可以划分为3t个集合X1，…，X3t，使得对任意i，在Xi上导出的子图没有大于t的分支.这个推论改进了Wood（2010）[21]的一个结果，该结果指出V（G）可以被划分成n × 3.5 t+ 2 n × 10 t这样的集合。
We prove that for every graph H, if a graph G has no (odd) H minor, then its vertex set V (G) can be partitioned into three sets X 1, X 2, X 3 such that for each i, the subgraph induced on X i has no component of size larger than a function of H and the maximum degree of G. This improves a previous result of Alon, Ding, Oporowski and Vertigan (2003)[1] stating that V (G) can be partitioned into four such sets if G has no H minor. Our theorem generalizes a result of Esperet and Joret (2014)[9], who proved it for graphs embeddable on a fixed surface and asked whether it is true for graphs with no H minor. As a corollary, we prove that for every positive integer t, if a graph G has no K t+ 1 minor, then its vertex set V (G) can be partitioned into 3t sets X 1,…, X 3 t such that for each i, the subgraph induced on X i has no component of size larger than a function of t. This corollary improves a result of Wood (2010)[21], which states that V (G) can be partitioned into⌈ 3.5 t+ 2⌉ such sets.