Pure Pairs. V. Excluding Some Long Subdivision
Pure Pairs. V. Excluding Some Long Subdivision
复制标题
纯对。
DOI：
10.1007/s00493-023-00025-8
复制
发表时间：
2023
期刊：
影响因子：
1.1
通讯作者：
Spirkl, Sophie
中科院分区：
文献类型：
--
作者：
Scott, Alex;Seymour, Paul;Spirkl, Sophie
图G中的“纯对”是V（G）的不相交子集的对A，B，使得A是B的完全或反完全。Jacob Fox证明了，对于所有的图，存在一个具有n个顶点的可比图G，其中n是大的，其中不存在纯对A，B。他还证明了，对于所有存在，使得对于每一个具有顶点的可比图G，存在一个纯对A，B;并证明了这同样适用于每一个完美图G。我们证明这个猜想，并加强它在几个方面。特别地，我们证明了，对所有，和所有，存在使得，如果G是一个-顶点图，没有长度精确的洞，也没有长度精确的反洞，则存在一个纯对A，BinG，和。这是进一步加强，取代排除洞排除一些“长”细分的一般图。
A “pure pair” in a graphGis a pairA,Bof disjoint subsets ofV(G) such thatAis complete or anticomplete toB. Jacob Fox showed that for all, there is a comparability graphGwithnvertices, wherenis large, in which there is no pure pairA,Bwith. He also proved that for allthere existssuch that for every comparability graphGwithvertices, there is a pure pairA,Bwith; and conjectured that the same holds for every perfect graphG. We prove this conjecture and strengthen it in several ways. In particular, we show that for all, and all, there existssuch that, ifGis an-vertex graph with no hole of length exactlyand no antihole of length exactly, then there is a pure pairA,BinGwithand. This is further strengthened, replacing excluding a hole by excluding some “long” subdivision of a general graph.
登录
查看更多内容
DOI：
--
发表时间：
2022
期刊：
影响因子：
--
作者：
A. Scott;P. Seymour;S. Spirkl;M. Chudnovsky
通讯作者：
M. Chudnovsky
影响因子：
0.8
作者：
V. Rödl
通讯作者：
V. Rödl
埃尔多斯哈伊纳尔的毛毛虫
DOI：
--
发表时间：
2019
期刊：
Journal of combinatorial theory. Series B (Print)
影响因子：
--
作者：
Anita Liebenau;Marcin Pilipczuk;P. Seymour;S. Spirkl
通讯作者：
S. Spirkl
DOI：
--
发表时间：
2018
期刊：
影响因子：
--
作者：
M. Chudnovsky;A. Scott;P. Seymour;S. Spirkl
通讯作者：
S. Spirkl
归纳拉姆齐型定理
DOI：
--
发表时间：
2007
期刊：
Electron. Notes Discret. Math.
影响因子：
--
作者：
J. Fox;B. Sudakov
通讯作者：
B. Sudakov