Characterising graphs with no subdivision of a wheel of bounded diameter

Johannes Carmesin

doi:10.1016/j.jctb.2023.01.004

Characterising graphs with no subdivision of a wheel of bounded diameter

Johannes Carmesin

Mathematics

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

86 Downloads (Pure)

Abstract

We prove that a graph has an r-bounded subdivision of a wheel if and only if it does not have a graph-decomposition of locality r and width at most two.

Original language	English
Pages (from-to)	21-51
Number of pages	31
Journal	Journal of Combinatorial Theory. Series B
Volume	161
Early online date	10 Feb 2023
DOIs	https://doi.org/10.1016/j.jctb.2023.01.004
Publication status	Published - 1 Jul 2023

Keywords

Graph minor
Characterisation of graph classes
Shallow minors
Local separators
Graph decompositions
Duality theorem

Access to Document

10.1016/j.jctb.2023.01.004Licence: Creative Commons: Attribution (CC BY)

Carmesin2023_Characterising_graphsFinal published version, 612 KBLicence: Creative Commons: Attribution (CC BY)

Graph Minors in three dimensions and Connectivity
Carmesin, J. (Principal Investigator)
Engineering & Physical Science Research Council
1/09/20 → 7/07/24
Project: Research Councils

Cite this

@article{f9a7c0bb19dd4de49219a7b4092e26f3,

title = "Characterising graphs with no subdivision of a wheel of bounded diameter",

abstract = "We prove that a graph has an r-bounded subdivision of a wheel if and only if it does not have a graph-decomposition of locality r and width at most two.",

keywords = "Graph minor, Characterisation of graph classes, Shallow minors, Local separators, Graph decompositions, Duality theorem",

author = "Johannes Carmesin",

year = "2023",

month = jul,

day = "1",

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

language = "English",

volume = "161",

pages = "21--51",

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

issn = "0095-8956",

publisher = "Elsevier",

}

TY - JOUR

T1 - Characterising graphs with no subdivision of a wheel of bounded diameter

AU - Carmesin, Johannes

PY - 2023/7/1

Y1 - 2023/7/1

N2 - We prove that a graph has an r-bounded subdivision of a wheel if and only if it does not have a graph-decomposition of locality r and width at most two.

AB - We prove that a graph has an r-bounded subdivision of a wheel if and only if it does not have a graph-decomposition of locality r and width at most two.

KW - Graph minor

KW - Characterisation of graph classes

KW - Shallow minors

KW - Local separators

KW - Graph decompositions

KW - Duality theorem

U2 - 10.1016/j.jctb.2023.01.004

DO - 10.1016/j.jctb.2023.01.004

M3 - Article

SN - 0095-8956

VL - 161

SP - 21

EP - 51

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Characterising graphs with no subdivision of a wheel of bounded diameter

Abstract

Keywords

Access to Document

Fingerprint

Projects

Graph Minors in three dimensions and Connectivity

Cite this