BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Max Pitz appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
Halin conjectured 20 years ago that a graph has a normal spanning tree if and only if every minor of it has countable colouring number. We prove Halin's conjecture. This implies a forbidden minor characterisation for the property of having a normal spanning tree.
We show that every connected graph can be approximated by a normal tree, up to some arbitrarily small error phrased in terms of neighbourhoods around its ends. The existence of such approximate normal trees has consequences of both combinatorial and topological nature. On the combinatorial side, we show that a graph has a normal spanning tree as soon as it has normal spanning trees locally at each end; i.e., the only obstruction for a graph to having a normal spanning tree is an end for which none of its neighbourhoods has a normal spanning tree. On the topological side, we show that the end space $Ω(G)$, as well as the spaces $|G| = G \cup Ω(G)$ naturally associated with a graph $G$, are always paracompact. This gives unified and short proofs for a number of results by Diestel, Sprüssel and Polat, and answers an open question about metrizability of end spaces by Polat.
In a paper from 2001 (Journal of the LMS), Diestel and Leader offered a proof that a connected graph has a normal spanning tree if and only if it does not contain a minor from two specific forbidden classes of graphs, all of cardinality $\aleph_1$. Unfortunately, their proof contains a gap, and their result is incorrect. In this paper, we construct a third type of obstruction: an $\aleph_1$-sized graph without a normal spanning tree that contains neither of the two types described by Diestel and Leader as a minor. Further, we show that any list of forbidden minors characterising the graphs with normal spanning trees must contain graphs of arbitrarily large cardinality.
A simplified construction is presented for Komjáth's result that for every uncountable cardinal $κ$, there are $2^κ$ graphs of size $κ$ none of them being a minor of another.
We show that a graph $G$ has a normal spanning tree if and only if its vertex set is the union of countably many sets each separated from any subdivided infinite clique in $G$ by a finite set of vertices. This proves a conjecture by Brochet and Diestel from 1994, giving a common strengthening of two classical normal spanning tree criterions due to Jung and Halin. Moreover, our method gives a new, algorithmic proof of Halin's theorem that every connected graph not containing a subdivision of a countable clique has a normal spanning tree.
We present two short proofs for Diestel's criterion that a connected graph has a normal spanning tree provided it contains no subdivision of a countable clique in which every edge has been replaced by uncountably many parallel edges.
A compact graph-like space is a triple $(X,V,E)$ where $X$ is a compact, metrizable space, $V \subseteq X$ is a closed zero-dimensional subset, and $E$ is an index set such that $X \setminus V \cong E \times (0,1)$. New characterizations of compact graph-like spaces are given, connecting them to certain classes of continua, and to standard subspaces of Freudenthal compactifications of locally finite graphs. These are applied to characterize Eulerian graph-like compacta.