A Stallings type theorem for quasi-transitive graphs

Matthias Hamann; Florian Lehner; Babak Miraftab; Tim Rühmann

doi:10.1016/j.jctb.2022.05.008

A Stallings type theorem for quasi-transitive graphs

Matthias Hamann, Florian Lehner, Babak Miraftab, Tim Rühmann

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

Abstract

We consider locally finite, connected, quasi-transitive graphs and show that every such graph with more than one end is a tree amalgamation of two other such graphs. This can be seen as a graph-theoretical version of Stallings' splitting theorem for multi-ended finitely generated groups and indeed it implies this theorem. Our result also leads to a characterisation of accessible graphs. We obtain applications of our results for planar graphs (answering a variant of a question by Mohar in the affirmative) and graphs without thick ends.

Original language	English
Pages (from-to)	40-69
Number of pages	30
Journal	Journal of Combinatorial Theory. Series B
Volume	157
DOIs	https://doi.org/10.1016/j.jctb.2022.05.008
Publication status	Published - Nov 2022
Externally published	Yes

Keywords

Infinite graphs
Transitivity
Tree-decompositions

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/j.jctb.2022.05.008

Cite this

@article{9f4f54076c0e4ddf8a449a7888308b65,

title = "A Stallings type theorem for quasi-transitive graphs",

abstract = "We consider locally finite, connected, quasi-transitive graphs and show that every such graph with more than one end is a tree amalgamation of two other such graphs. This can be seen as a graph-theoretical version of Stallings' splitting theorem for multi-ended finitely generated groups and indeed it implies this theorem. Our result also leads to a characterisation of accessible graphs. We obtain applications of our results for planar graphs (answering a variant of a question by Mohar in the affirmative) and graphs without thick ends.",

keywords = "Infinite graphs, Transitivity, Tree-decompositions",

author = "Matthias Hamann and Florian Lehner and Babak Miraftab and Tim R{\"u}hmann",

note = "Funding Information: Supported by the European Research Council under the European Union Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement n∘ 617747 and through the Heisenberg-Programme of the Deutsche Forschungsgemeinschaft (DFG Grant HA 8257/1-1).Supported by the Austrian Science Fund (FWF), grant J 3850-N32. Publisher Copyright: {\textcopyright} 2022 Elsevier Inc.",

year = "2022",

month = nov,

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

language = "English",

volume = "157",

pages = "40--69",

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

issn = "0095-8956",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - A Stallings type theorem for quasi-transitive graphs

AU - Hamann, Matthias

AU - Lehner, Florian

AU - Miraftab, Babak

AU - Rühmann, Tim

N1 - Funding Information: Supported by the European Research Council under the European Union Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement n∘ 617747 and through the Heisenberg-Programme of the Deutsche Forschungsgemeinschaft (DFG Grant HA 8257/1-1).Supported by the Austrian Science Fund (FWF), grant J 3850-N32. Publisher Copyright: © 2022 Elsevier Inc.

PY - 2022/11

Y1 - 2022/11

N2 - We consider locally finite, connected, quasi-transitive graphs and show that every such graph with more than one end is a tree amalgamation of two other such graphs. This can be seen as a graph-theoretical version of Stallings' splitting theorem for multi-ended finitely generated groups and indeed it implies this theorem. Our result also leads to a characterisation of accessible graphs. We obtain applications of our results for planar graphs (answering a variant of a question by Mohar in the affirmative) and graphs without thick ends.

AB - We consider locally finite, connected, quasi-transitive graphs and show that every such graph with more than one end is a tree amalgamation of two other such graphs. This can be seen as a graph-theoretical version of Stallings' splitting theorem for multi-ended finitely generated groups and indeed it implies this theorem. Our result also leads to a characterisation of accessible graphs. We obtain applications of our results for planar graphs (answering a variant of a question by Mohar in the affirmative) and graphs without thick ends.

KW - Infinite graphs

KW - Transitivity

KW - Tree-decompositions

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

U2 - 10.1016/j.jctb.2022.05.008

DO - 10.1016/j.jctb.2022.05.008

M3 - Article

AN - SCOPUS:85132560587

SN - 0095-8956

VL - 157

SP - 40

EP - 69

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

A Stallings type theorem for quasi-transitive graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this