On Andreae's ubiquity conjecture

Johannes Carmesin

doi:10.1016/j.jctb.2023.04.002

On Andreae's ubiquity conjecture

Johannes Carmesin

Mathematics

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

58 Downloads (Pure)

Abstract

A graph H is ubiquitous if every graph G that for every natural number n contains n vertex-disjoint H-minors contains infinitely many vertex-disjoint H-minors. Andreae conjectured that every locally finite graph is ubiquitous. We give a disconnected counterexample to this conjecture. It remains open whether every connected locally finite graph is ubiquitous.

Original language	English
Pages (from-to)	68-70
Number of pages	3
Journal	Journal of Combinatorial Theory. Series B
Volume	162
Early online date	5 May 2023
DOIs	https://doi.org/10.1016/j.jctb.2023.04.002
Publication status	Published - 1 Sept 2023

Keywords

Infinite graph
Ubiquity
Minors
Andreae Conjecture
Well-quasi ordering

Access to Document

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

Carmesin2023_On_Andreae's_ubiquity_conjectureFinal published version, 201 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 → 31/08/25
Project: Research Councils

Cite this

@article{4353ff55abda4e2fb6b30b092453e5e4,

title = "On Andreae's ubiquity conjecture",

abstract = "A graph H is ubiquitous if every graph G that for every natural number n contains n vertex-disjoint H-minors contains infinitely many vertex-disjoint H-minors. Andreae conjectured that every locally finite graph is ubiquitous. We give a disconnected counterexample to this conjecture. It remains open whether every connected locally finite graph is ubiquitous.",

keywords = "Infinite graph, Ubiquity, Minors, Andreae Conjecture, Well-quasi ordering",

author = "Johannes Carmesin",

year = "2023",

month = sep,

day = "1",

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

language = "English",

volume = "162",

pages = "68--70",

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

issn = "0095-8956",

publisher = "Elsevier",

}

TY - JOUR

T1 - On Andreae's ubiquity conjecture

AU - Carmesin, Johannes

PY - 2023/9/1

Y1 - 2023/9/1

N2 - A graph H is ubiquitous if every graph G that for every natural number n contains n vertex-disjoint H-minors contains infinitely many vertex-disjoint H-minors. Andreae conjectured that every locally finite graph is ubiquitous. We give a disconnected counterexample to this conjecture. It remains open whether every connected locally finite graph is ubiquitous.

AB - A graph H is ubiquitous if every graph G that for every natural number n contains n vertex-disjoint H-minors contains infinitely many vertex-disjoint H-minors. Andreae conjectured that every locally finite graph is ubiquitous. We give a disconnected counterexample to this conjecture. It remains open whether every connected locally finite graph is ubiquitous.

KW - Infinite graph

KW - Ubiquity

KW - Minors

KW - Andreae Conjecture

KW - Well-quasi ordering

U2 - 10.1016/j.jctb.2023.04.002

DO - 10.1016/j.jctb.2023.04.002

M3 - Article

SN - 0095-8956

VL - 162

SP - 68

EP - 70

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

On Andreae's ubiquity conjecture

Abstract

Keywords

Access to Document

Fingerprint

Projects

Graph Minors in three dimensions and Connectivity

Cite this