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ć

doi:10.1016/j.jctb.2024.04.006

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ć

Mathematics

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

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 language	English (US)
Pages (from-to)	96-158
Number of pages	63
Journal	Journal of Combinatorial Theory. Series B
Volume	168
DOIs	https://doi.org/10.1016/j.jctb.2024.04.006
State	Published - Sep 2024

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Cycle
Hole
Structure theorem

Access to Document

10.1016/j.jctb.2024.04.006

Cite this

@article{1487c8b1bbc947a29e6f55f50629dda3,

title = "Graphs with all holes the same length",

abstract = "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.",

keywords = "Cycle, Hole, Structure theorem",

author = "Linda Cook and Jake Horsfield and Myriam Preissmann and Cl{\'e}oph{\'e}e Robin and Paul Seymour and \{Luh Dewi Sintiari\}, Ni and Nicolas Trotignon and Kristina Vu{\v s}kovi{\'c}",

note = "Publisher Copyright: {\textcopyright} 2024",

year = "2024",

month = sep,

doi = "10.1016/j.jctb.2024.04.006",

language = "English (US)",

volume = "168",

pages = "96--158",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Graphs with all holes the same length

AU - Cook, Linda

AU - Horsfield, Jake

AU - Preissmann, Myriam

AU - Robin, Cléophée

AU - Seymour, Paul

AU - Luh Dewi Sintiari, Ni

AU - Trotignon, Nicolas

AU - Vušković, Kristina

PY - 2024/9

Y1 - 2024/9

N2 - 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.

AB - 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.

KW - Cycle

KW - Hole

KW - Structure theorem

UR - https://www.scopus.com/pages/publications/85192844185

UR - https://www.scopus.com/pages/publications/85192844185#tab=citedBy

U2 - 10.1016/j.jctb.2024.04.006

DO - 10.1016/j.jctb.2024.04.006

M3 - Article

AN - SCOPUS:85192844185

SN - 0095-8956

VL - 168

SP - 96

EP - 158

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Graphs with all holes the same length

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this