论文标题
纯对。 iv。两分图中的树木
Pure pairs. IV. Trees in bipartite graphs
论文作者
论文摘要
在本文中，我们调查了强烈的Erdos-Hajnal特性的两分类似物。我们证明，对于每个森林$ h $和每$τ> 0 $都存在$ε> 0 $，这样，如果$ g $具有两部分$（a，b）$，并且不包含$ h $作为诱导子摄影，并且最多有$（1-τ）| a | \ cdot | b | b | b | g $ g $ | | | | $ v_i $，$ i = 1,2 $。除了森林拥有此财产外，没有图形$ h $。
In this paper we investigate the bipartite analogue of the strong Erdos-Hajnal property. We prove that for every forest $H$ and every $τ>0$ there exists $ε>0$, such that if $G$ has a bipartition $(A,B)$ and does not contain $H$ as an induced subgraph, and has at most $(1-τ)|A|\cdot|B|$ edges, then there is a stable set in $G$ that contains at least $ε|V_i|$ vertices of $V_i$, for $i=1,2$. No graphs $H$ except forests have this property.
