Graphs with all holes the same length

Linda Cook, Jake Horsfield, Myriam Preissmann, Cléophée Robin, Paul Seymour, Ni Luh Dewi Sintiari, Nicolas Trotignon, Kristina Vušković

Research output: Contribution to journalArticlepeer-review


A graph is ℓ-holed if all its induced cycles of length at least four have length exactly ℓ. We give a complete description of the ℓ-holed graphs for each ℓ≥7.

Original languageEnglish (US)
Pages (from-to)96-158
Number of pages63
JournalJournal of Combinatorial Theory. Series B
StatePublished - Sep 2024

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


  • Cycle
  • Hole
  • Structure theorem


Dive into the research topics of 'Graphs with all holes the same length'. Together they form a unique fingerprint.

Cite this