{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,23]],"date-time":"2026-01-23T10:38:56Z","timestamp":1769164736902,"version":"3.49.0"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>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}) &gt; 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$.\r\nOn 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.<\/jats:p>","DOI":"10.37236\/12111","type":"journal-article","created":{"date-parts":[[2024,5,31]],"date-time":"2024-05-31T13:39:06Z","timestamp":1717162746000},"source":"Crossref","is-referenced-by-count":1,"title":["Strong Erd\u0151s-Hajnal Properties in Chordal Graphs"],"prefix":"10.37236","volume":"31","author":[{"given":"Minho","family":"Cho","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Holmsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jinha","family":"Kim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Minki","family":"Kim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"23455","published-online":{"date-parts":[[2024,5,31]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v31i2p37\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v31i2p37\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,31]],"date-time":"2024-05-31T13:39:06Z","timestamp":1717162746000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v31i2p37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,31]]},"references-count":0,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2024,4,5]]}},"URL":"https:\/\/doi.org\/10.37236\/12111","relation":{},"ISSN":["1077-8926"],"issn-type":[{"value":"1077-8926","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,31]]},"article-number":"P2.37"}}