← All problems

Seymour’s cograph question for chordal graphs

For a graph GG, let cg⁡(G)\operatorname{cg}(G) be the maximum integer kk such that GG contains an induced subgraph on kk vertices that is a cograph. Is there an absolute constant C>0C>0 such that, for every integer n≥2n\ge 2, some nn-vertex chordal graph GG satisfies cg⁡(G)≤Cn/log⁡n\operatorname{cg}(G)\le Cn/\log n? Equivalently, is the general lower bound cg⁡(G)≥n/(2log⁡n)\operatorname{cg}(G)\ge n/(2\log n) for nn-vertex chordal graphs optimal up to a constant factor?

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

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 nn-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 n/(2log⁡n)n/(2\log n) 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.