Induced subgraphs and tree decompositions XIV. Non-adjacent neighbours in a hole

Maria Chudnovsky; Sepehr Hajebi; Sophie Spirkl

doi:10.1016/j.ejc.2024.104074

Induced subgraphs and tree decompositions XIV. Non-adjacent neighbours in a hole

Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl

Mathematics

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

Abstract

A clock is a graph consisting of an induced cycle C and a vertex not in C with at least two non-adjacent neighbours in C. We show that every clock-free graph of large treewidth contains a “basic obstruction” of large treewidth as an induced subgraph: a complete graph, a subdivision of a wall, or the line graph of a subdivision of a wall.

Original language	English (US)
Article number	104074
Journal	European Journal of Combinatorics
Volume	124
DOIs	https://doi.org/10.1016/j.ejc.2024.104074
State	Published - Feb 2025

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.ejc.2024.104074

Cite this

@article{3a587be23a3641e2b0c23ea5c885b9fe,

title = "Induced subgraphs and tree decompositions XIV. Non-adjacent neighbours in a hole",

abstract = "A clock is a graph consisting of an induced cycle C and a vertex not in C with at least two non-adjacent neighbours in C. We show that every clock-free graph of large treewidth contains a “basic obstruction” of large treewidth as an induced subgraph: a complete graph, a subdivision of a wall, or the line graph of a subdivision of a wall.",

author = "Maria Chudnovsky and Sepehr Hajebi and Sophie Spirkl",

note = "Publisher Copyright: {\textcopyright} 2024 The Author(s)",

year = "2025",

month = feb,

doi = "10.1016/j.ejc.2024.104074",

language = "English (US)",

volume = "124",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press",

}

TY - JOUR

T1 - Induced subgraphs and tree decompositions XIV. Non-adjacent neighbours in a hole

AU - Chudnovsky, Maria

AU - Hajebi, Sepehr

AU - Spirkl, Sophie

PY - 2025/2

Y1 - 2025/2

N2 - A clock is a graph consisting of an induced cycle C and a vertex not in C with at least two non-adjacent neighbours in C. We show that every clock-free graph of large treewidth contains a “basic obstruction” of large treewidth as an induced subgraph: a complete graph, a subdivision of a wall, or the line graph of a subdivision of a wall.

AB - A clock is a graph consisting of an induced cycle C and a vertex not in C with at least two non-adjacent neighbours in C. We show that every clock-free graph of large treewidth contains a “basic obstruction” of large treewidth as an induced subgraph: a complete graph, a subdivision of a wall, or the line graph of a subdivision of a wall.

UR - http://www.scopus.com/inward/record.url?scp=85204620148&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85204620148&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2024.104074

DO - 10.1016/j.ejc.2024.104074

M3 - Article

AN - SCOPUS:85204620148

SN - 0195-6698

VL - 124

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

M1 - 104074

ER -

Induced subgraphs and tree decompositions XIV. Non-adjacent neighbours in a hole

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this