Erdős–Hajnal for graphs with no 5‐hole
Erdős–Hajnal for graphs with no 5‐hole
复制标题
ErdÅsâHajnal 用于没有 5 孔的图
DOI：
10.1112/plms.12504
复制
发表时间：
2023
影响因子：
1.8
通讯作者：
Spirkl, Sophie
中科院分区：
文献类型：
--
作者：
Chudnovsky, Maria;Scott, Alex;Seymour, Paul;Spirkl, Sophie
Erdens-Hajnal猜想认为，对每个图H$H$，存在τ>0$\tau >0$使得每个不含H$H$作为导出子图的图G$G$至少有一个团或稳定的基数集|G| τ$|G| ^\tau$.我们证明了当H$H$是一个长度为5的圈时，这是正确的。我们还证明了几个进一步的结果：例如，如果C$C$是一个圈，H$H$是一个森林的补图，则存在τ> 0 $\tau>0$使得每个不包含C，H$C，H$作为导出子图的图G$G$至少有一个团或稳定的基数集|G| τ$|G| ^\tau$.
The Erdős–Hajnal conjecture says that for every graph H$H$ there exists τ>0$\tau >0$ such that every graph G$G$ not containing H$H$ as an induced subgraph has a clique or stable set of cardinality at least |G|τ$|G|^\tau$. We prove that this is true when H$H$ is a cycle of length five. We also prove several further results: for instance, that if C$C$ is a cycle and H$H$ is the complement of a forest, there exists τ>0$\tau >0$ such that every graph G$G$ containing neither of C,H$C,H$ as an induced subgraph has a clique or stable set of cardinality at least |G|τ$|G|^\tau$.