Strong Erdős–Hajnal properties in chordal graphs

Abstract

A graph class G has the strong Erdő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 (Formula presented). 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ő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 F1, F2 of subtree families of the same size in a tree T with k leaves, there exists subfamilies (Formula presented) such that either every pair of representatives from distinct subfamilies intersect or every such pair do not intersect. Our results are asymptotically optimal. © The authors.