Cographs in chordal graphs
En palabras de los autores
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 .
Resultado principalEl resumen no menciona limitaciones.
Apareció: viernes, 23 de octubre. arXiv. Preprint, todavía sin revisión por pares.