pipette
ESEspañol

Cographs in chordal graphs

Sepehr Hajebi

Preprint

In the authors' words

For a graph , let be the maximum for which contains a -vertex cograph as an induced subgraph. The Erd\H{o}s-Hajnal conjecture asserts that for every proper hereditary graph class , there exists such that every -vertex graph satisfies . This is still open; however, for some hereditary classes, one may guarantee much stronger bounds. For instance, every chordal graph on vertices satisfies . Paul Seymour asked whether this bound is optimal up to a constant factor. We answer this affirmatively, even for interval graphs: For every integer , we construct an -vertex interval graph with .

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 23. arXiv. Preprint, not yet peer-reviewed.