Strong Erdős-Hajnal Properties in Chordal Graphs

A graph class G has the strong Erd{ o}s--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 Km, m 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{ o}s--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 θ ( ln k/k | F₁ |) such that either every pair of representatives from distinct subfamilies intersect or every such pair do not intersect. Our results are asymptotically optimal.