论文标题
字符串图具有Erdős-Hajnal属性
String graphs have the Erdős-Hajnal property
论文作者
论文摘要
字符串图是平面曲线的交点图。我们证明存在一个绝对常数$ c> 0 $，因此，如果$ g $是$ n $ vertices上的字符串图，则$ g $包含一个集团或独立大小的独立集，至少$ n^{c} $。
A string graph is the intersection graph of curves in the plane. We prove that there exists an absolute constant $c>0$ such that if $G$ is a string graph on $n$ vertices, then $G$ contains either a clique or an independent set of size at least $n^{c}$.
