Seymour’s cograph question for chordal graphs
For a graph , let be the maximum integer such that contains an induced subgraph on vertices that is a cograph. Is there an absolute constant such that, for every integer , some -vertex chordal graph satisfies ? Equivalently, is the general lower bound for -vertex chordal graphs optimal up to a constant factor?
References
- Cographs in chordal graphs — arXiv — Sepehr Hajebi
Source: arXiv
Progress summary
A new preprint claims the best possible scale for large induced cographs in chordal graphs, already within the narrower interval-graph class.
Seymour’s question asks how large an induced cograph must occur in an -vertex chordal graph. The latest result addresses the scale of this extremal quantity, rather than the broader Erdős–Hajnal conjecture.
Interval-graph bound — October 2026
Sepehr Hajebi’s preprint claims that the lower bound is optimal up to a constant even for interval graphs, a subclass of chordal graphs. Thus the chordal-graph optimization problem is claimed settled up to constant factors, while no resolution of the broader hereditary-class conjecture is asserted.
Current status (as of October 2026): The order of magnitude is claimed settled up to constants, already for interval graphs, but the preprint’s result remains unverified and the broader Erdős–Hajnal conjecture remains open.
Sources
Solutions 0
No solutions have been posted yet.