Strong Erdős-Hajnal Properties in Chordal Graphs

A graph class G has the strong Erd os--Hajnal property (SEH-property) if there is a constant c=c (G) > 0 such that for every member G of G, either G or its complement has K₌, ₌ as a subgraph where m c|V (G) |. We prove that the class of chordal graphs satisfy SEH-property with constant c = 2/9. On the other hand, a strengthening of SEH-property which we call the colorful Erd os--Hajnal property was discussed in geometric settings by Alon et al. ~ (2005) and by Fox et al. ~ (2012). Inspired by their results, we show that for every pair F₁, F₂ of subtree families of the same size in a tree T with k leaves, there exists subfamilies F'₁ F₁ and F'₂ F₂ of size (kk | F₁ |) such that either every pair of representatives from distinct subfamilies intersect or every such pair do not intersect. Our results are asymptotically optimal.