Skip to content
DraconiticResearch
Search Sources API
182,469 studies31 sourcesUpdated 6 min ago
PreprintarXiv licencearXiv

Cographs in chordal graphs

  • Sepehr Hajebi
Open at sourcePDFDOICite

Abstract

For a graph G, let cg(G) be the maximum k∈ ℕ 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 𝒢, there exists γ∈(0,1] such that every n-vertex graph G∈𝒢 satisfies cg(G)≥ nγ. This is still open; however, for some hereditary classes, one may guarantee much stronger bounds. For instance, every chordal graph G on n≥ 2 vertices satisfies cg(G)≥ n/(2log n). Paul Seymour asked whether this bound is optimal up to a constant factor. We answer this affirmatively, even for interval graphs: For every integer n≥ 2, we construct an n-vertex interval graph G with cg(G)<64n/log n.

Related

  1. Counting cographs in locally dense graphs
    Hyunwoo Lee
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. The multiplicative Merino--Welsh inequality for chordal graphs
    Shaohan Xu, Fengming Dong, Kexiang Xu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. There are no nontrivial chordal square-complementary graphs
    Pierre Aboulker, Martin Milanič, Peter Muršič +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. On Hypergraph Colorings and Completely Independent Spanning Trees in Chordal Graphs
    Mohammed Lalou, Nader Mbarek, Abdallah Skender +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Maximum Edge Open Packing on AT-Free, Chordal, and Convex Bipartite Graphs
    Gautam K. Das, Kamal Santra
    arXivPreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{hajebi2026cographs,
  title = {{Cographs in chordal graphs}},
  author = {Sepehr Hajebi},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.30299},
  eprint = {2610.30299},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.30299},
}
RIS
TY  - UNPB
TI  - Cographs in chordal graphs
AU  - Sepehr Hajebi
PY  - 2026
DA  - 2026/10/21
PB  - arXiv
DO  - 10.48550/arxiv.2610.30299
UR  - https://arxiv.org/abs/2610.30299
AB  - For a graph G, let cg(G) be the maximum k∈ ℕ 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 𝒢, there exists γ∈(0,1] such that every n-vertex graph G∈𝒢 satisfies cg(G)≥ n^γ. This is still open; however, for some hereditary classes, one may guarantee much stronger bounds. For instance, every chordal graph G on n≥ 2 vertices satisfies cg(G)≥ n/(2log n). Paul Seymour asked whether this bound is optimal up to a constant factor. We answer this affirmatively, even for interval graphs: For every integer n≥ 2, we construct an n-vertex interval graph G with cg(G)<64n/log n.
ER  -