Strong Erdős-Hajnal properties in chordal graphs

Abstract

A graph class $\mathcal{G}$ has the strong Erdős-Hajnal property (SEH-property) if there is a constant $c=c(\mathcal{G})>0$ such that for every member $G$ of $\mathcal{G}$, either $G$ or its complement has $K_{m,m}$ as a subgraph where $m\ge \lfloor c|V(G)|\rfloor$. 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 $F_1,F_2$ of subtree families of the same size in a tree $T$ with $k$ leaves, there exists subfamilies $F_1^{\prime }\subseteq F_1$ and $F_2^{\prime }\subseteq F_2$ of size $\theta \left(\frac{\ln k}{k}\left|F_1\right|\right)$ such that either every pair of representatives from distinct subfamilies intersect or every such pair do not intersect. Our results are asymptotically optimal.

17 pages