Pure Pairs. II. Excluding All Subdivisions of A Graph
Pure Pairs. II. Excluding All Subdivisions of A Graph
复制标题
纯对。
DOI：
10.1007/s00493-020-4024-1
复制
发表时间：
2021
期刊：
影响因子：
1.1
通讯作者：
Spirkl, Sophie
中科院分区：
文献类型：
--
作者：
Chudnovsky, Maria;Scott, Alex;Seymour, Paul;Spirkl, Sophie
我们证明对于每个图 H 都存在 ɛ > 0，这样，对于每个 |G|≥2 的图 G，如果没有 G 的诱导子图是 H 的细分，那么 G 的某个顶点至少有 ɛ|G|邻居，或者有两个不相交的集合 A,B⊆V(G) 且 |A|,|B|≥ɛ|G|这样就没有边连接 A 和 B。由此可见，对于每个图 H，都存在 c>0，使得对于每个图 G，如果没有 G 的导出子图或者其补图是 H 的细分，则 G 至少有一个集团或稳定的基数集 |G|c。这与 Erdős-Hajnal 猜想有关。
We prove for every graphHthere exists ɛ > 0 such that, for every graphGwith |G|≥2, if no induced subgraph ofGis a subdivision ofH, then either some vertex ofGhas at least ɛ|G| neighbours, or there are two disjoint setsA,B⊆V(G) with |A|,|B|≥ɛ|G| such that no edge joinsAandB. It follows that for every graphH, there existsc>0 such that for every graphG, if no induced subgraph ofGor its complement is a subdivision ofH, thenGhas a clique or stable set of cardinality at least |G|c. This is related to the Erdős-Hajnal conjecture.
登录
查看更多内容
DOI：
--
发表时间：
2015
期刊：
Journal of combinatorial theory. Series B (Print)
影响因子：
--
作者：
A. Scott;P. Seymour
通讯作者：
P. Seymour
具有大色数的图的归纳子图 VII。
DOI：
--
发表时间：
2017
期刊：
Journal of combinatorial theory. Series B (Print)
影响因子：
--
作者：
A. Scott;P. Seymour
通讯作者：
P. Seymour
DOI：
10.37236/6768
发表时间：
2017-02
期刊：
Electron. J. Comb.
影响因子：
--
作者：
A. Scott;P. Seymour
通讯作者：
A. Scott;P. Seymour
影响因子：
0.8
作者：
V. Rödl
通讯作者：
V. Rödl
影响因子：
1.1
作者：
A. Scott;P. Seymour
通讯作者：
P. Seymour