Caterpillars in Erdos-Hajnal

摘要

Let T be a tree such that all its vertices of degree more than two lie on one path; that is, T is a caterpillar subdivision. We prove that there exists epsilon > 0 such that for every graph G with vertical bar V(G)vertical bar >= 2 not containing T as an induced subgraph, either some vertex has at least epsilon vertical bar V(G)vertical bar neighbours, or there are two disjoint sets of vertices A, B, both of cardinality at least epsilon vertical bar V(G)vertical bar, where there is no edge joining A and B.