Strong Erdős-Hajnal properties in chordal graphs

Minho Cho¹ ; Andreas Holmsen ; Jinha Kim ; Minki Kim

¹IBS ECOPRO

The electronic journal of combinatorics, Tome 31 (2024) no. 2

Résumé

A graph class $\mathcal{G}$ has the strong Erd{\H o}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 \geq \left\lfloor c|V(G)|\right\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{\H 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_1, F_2$ of subtree families of the same size in a tree $T$ with $k$ leaves, there exists subfamilies $F'_1 \subseteq F_1$ and $F'_2 \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.

Détail

DOI : 10.37236/12111

Classification : 05C69, 05C05, 05C35
Mots-clés : colorful Erdős-Hajnal property