On Andreae's ubiquity conjecture

DOI10.1016/J.JCTB.2023.04.002MaRDI QIDQ6170789zbMATH OpenOpenAlexFDO

Authors Johannes Carmesin

Publication date 10 August 2023

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2210.02711

zbMATH Keywords

ubiquityinfinite graphminorswell-quasi orderingAndreae conjecture

Mathematics Subject Classification ID

Infinite graphs (05C63) Graph minors (05C83)

Abstract: A graph $H$ is ubiquitous if for 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.

Recommendations

• Ubiquity of graphs with nowhere‐linear end structure
• scientific article; zbMATH DE number 3920529
• Topological ubiquity of trees
• Classes of locally finite ubiquitous graphs
• On disjoint configurations in infinite graphs

Cites work

• Classes of locally finite ubiquitous graphs
• On disjoint configurations in infinite graphs
• Topological ubiquity of trees
• Well-Quasi-Ordering Infinite Graphs with Forbidden Finite Planar Minor
• Über die Maximalzahl fremder unendlicher Wege in Graphen

Cited in

(5)

• scientific article; zbMATH DE number 22956 (Why is no real title available?)
• Ubiquity of oriented rays
• Ubiquity of graphs with nowhere‐linear end structure
• Ubiquity of locally finite graphs with extensive tree-decompositions
• Classes of locally finite ubiquitous graphs

This page was built for publication: On Andreae's ubiquity conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6170789)