Induced Subgraphs and Tree Decompositions VIII: Excluding a Forest in (Theta, Prism)-Free Graphs

Tara Abrishami; Bogdan Alecu; Maria Chudnovsky; Sepehr Hajebi; Sophie Spirkl

doi:10.1007/s00493-024-00097-0

Induced Subgraphs and Tree Decompositions VIII: Excluding a Forest in (Theta, Prism)-Free Graphs

Tara Abrishami, Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl

Mathematics

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

Abstract

Given a graph H, we prove that every (theta, prism)-free graph of sufficiently large treewidth contains either a large clique or an induced subgraph isomorphic to H, if and only if H is a forest.

Original language	English (US)
Pages (from-to)	921-948
Number of pages	28
Journal	Combinatorica
Volume	44
Issue number	5
DOIs	https://doi.org/10.1007/s00493-024-00097-0
State	Published - Oct 2024

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Computational Mathematics

Access to Document

10.1007/s00493-024-00097-0

Cite this

@article{bedcd0987bcb4485b79149206bbc68e7,

title = "Induced Subgraphs and Tree Decompositions VIII: Excluding a Forest in (Theta, Prism)-Free Graphs",

abstract = "Given a graph H, we prove that every (theta, prism)-free graph of sufficiently large treewidth contains either a large clique or an induced subgraph isomorphic to H, if and only if H is a forest.",

author = "Tara Abrishami and Bogdan Alecu and Maria Chudnovsky and Sepehr Hajebi and Sophie Spirkl",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive licence to J{\'a}nos Bolyai Mathematical Society and Springer-Verlag GmbH Germany, part of Springer Nature 2024.",

year = "2024",

month = oct,

doi = "10.1007/s00493-024-00097-0",

language = "English (US)",

volume = "44",

pages = "921--948",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "5",

}

TY - JOUR

T1 - Induced Subgraphs and Tree Decompositions VIII

T2 - Excluding a Forest in (Theta, Prism)-Free Graphs

AU - Abrishami, Tara

AU - Alecu, Bogdan

AU - Chudnovsky, Maria

AU - Hajebi, Sepehr

AU - Spirkl, Sophie

N1 - Publisher Copyright: © The Author(s), under exclusive licence to János Bolyai Mathematical Society and Springer-Verlag GmbH Germany, part of Springer Nature 2024.

PY - 2024/10

Y1 - 2024/10

N2 - Given a graph H, we prove that every (theta, prism)-free graph of sufficiently large treewidth contains either a large clique or an induced subgraph isomorphic to H, if and only if H is a forest.

AB - Given a graph H, we prove that every (theta, prism)-free graph of sufficiently large treewidth contains either a large clique or an induced subgraph isomorphic to H, if and only if H is a forest.

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

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

U2 - 10.1007/s00493-024-00097-0

DO - 10.1007/s00493-024-00097-0

M3 - Article

AN - SCOPUS:85189798165

SN - 0209-9683

VL - 44

SP - 921

EP - 948

JO - Combinatorica

JF - Combinatorica

IS - 5

ER -

Induced Subgraphs and Tree Decompositions VIII: Excluding a Forest in (Theta, Prism)-Free Graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this