Excluding paths and antipaths
Excluding paths and antipaths
复制标题
排除路径和反路径
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
P. Seymour
中科院分区：
文献类型：
--
作者：
M. Chudnovsky;P. Seymour
Erdős-Hajnal 猜想指出，对于每个图 H，都存在一个常数 δ(H)>0，这样，如果图 G 没有与 H 同构的导出子图，则 G 包含一个团或一个大小至少为 |V (G)|δ(H) 的稳定集。这个猜想仍然存在。我们考虑该猜想的一个变体，其中 H 和 Hc 都被排除，而不是排除 H 作为诱导子图。我们在 H 是五边路径的情况下证明了这个修改后的猜想。我们的第二个主要结果是其非对称版本：我们证明对于每个图 G，使得 G 不包含诱导的六边路径，并且 Gc 不包含诱导的四边路径，G 包含多项式大小的团或稳定集。
The Erdős-Hajnal conjecture states that for every graph H, there exists a constant δ(H)>0, such that if a graph G has no induced subgraph isomorphic to H, then G contains a clique or a stable set of size at least |V (G)|δ(H). This conjecture is still open. We consider a variant of the conjecture, where instead of excluding H as an induced subgraph, both H and Hc are excluded. We prove this modified conjecture for the case when H is the five-edge path. Our second main result is an asymmetric version of this: we prove that for every graph G such that G contains no induced six-edge path, and Gc contains no induced four-edge path, G contains a polynomial-size clique or stable set.