Strong Erdos-Hajnal properties in chordal graphs

Abstract

A graph class G has the strong Erdos-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-m,K-m as a subgraph where m >= left perpendicularc vertical bar V(G)vertical bar right perpendicular. 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 Erdos-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-1 , F-2 of subtree families of the same size in a tree T with k leaves, there exists subfamilies F-1' subset of F-1 and F-2' subset of F-2 of size theta (ln k/k vertical bar F-1 vertical bar) such that either every pair of representatives from distinct subfamilies intersect or every such pair do not intersect. Our results are asymptotically optimal.,