{"id":"arxiv/2610.30299","url":"https://arxiv.org/abs/2610.30299","tags":["math.CO"],"score":0,"title":"Cographs in chordal graphs","domain":"math.CO","source":"arxiv","authors":["Sepehr Hajebi"],"reviews":0,"subject":"math.CO","summary":"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 $γ\\in(0,1]$ such that every $n$-vertex graph $G\\in\\mathcal{G}$ satisfies $\\text{cg}(G)\\geq n^γ$. This is still open; however, for some hereditary classes, one may guarantee much stronger bounds. For instance, every chordal graph $G$ on $n\\geq 2$ vertices satisfies $\\text{cg}(G)\\geq n/(2\\log n)$. Paul Seymour asked whether this bound is optimal up to a…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-21","reactions":{}}