Cographs in chordal graphs

Abstract

For a graph $G$, let $\text{cg}(G)$ be the maximum $k\in \mathbb{N}$ for which $G$ contains a $k$-vertex cograph as an induced subgraph. The Erdős-Hajnal conjecture asserts that for every proper hereditary graph class $\mathcal{G}$, there exists $\gamma \in (0,1]$ such that every $n$-vertex graph $G\in \mathcal{G}$ satisfies $\text{cg}(G)\ge n^{\gamma }$. This is still open; however, for some hereditary classes, one may guarantee much stronger bounds. For instance, every chordal graph $G$ on $n\ge 2$ vertices satisfies $\text{cg}(G)\ge n/(2\log n)$. Paul Seymour asked whether this bound is optimal up to a constant factor. We answer this affirmatively, even for interval graphs: For every integer $n\ge 2$, we construct an $n$-vertex interval graph $G$ with $\text{cg}(G)<64n/\log n$.