论文标题
带有帽子和erdős-hajnal的孔
Holes with hats and Erdős-Hajnal
论文作者
论文摘要
图$ g $中的“孔 - 帽子”是$ g $的诱导子图，它由长度至少四个周期组成，再加上一个又有两个邻居，彼此相邻，彼此相邻两个邻居，而“房屋”是最小的，是最小的。尚不清楚是否存在$ε> 0 $，因此每个包含房屋的图形$ g $都有一组或稳定的基数，至少$ | g |^ε$;这是Erdős-Hajnal猜想的三个最小的开放式案例之一，并且是大量研究的主题。 我们证明存在$ε> 0 $，以便每个图$ g $无孔，帽子都有一组或稳定的基数，至少$ | g | g |^ε$
A "hole-with-hat" in a graph $G$ is an induced subgraph of $G$ that consists of a cycle of length at least four, together with one further vertex that has exactly two neighbours in the cycle, adjacent to each other, and the "house" is the smallest, on five vertices. It is not known whether there exists $ε>0$ such that every graph $G$ containing no house has a clique or stable set of cardinality at least $|G|^ε$; this is one of the three smallest open cases of the Erdős-Hajnal conjecture and has been the subject of much study. We prove that there exists $ε>0$ such that every graph $G$ with no hole-with-hat has a clique or stable set of cardinality at least $|G|^ε$
