BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Jan Kurkofka 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
Carmesin has extended Robertson and Seymour's tree-of-tangles theorem to the infinite tangles of locally finite infinite graphs. We extend it further to the infinite tangles of all infinite graphs. Our result has a number of applications for the topology of infinite graphs, such as their end spaces and their compactifications.
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.
The directions of an infinite graph $G$ are a tangle-like description of its ends: they are choice functions that choose compatibly for all finite vertex sets $X\subseteq V(G)$ a component of $G-X$. Although every direction is induced by a ray, there exist directions of graphs that are not uniquely determined by any countable subset of their choices. We characterise these directions and their countably determined counterparts in terms of star-like substructures or rays of the graph. Curiously, there exist graphs whose directions are all countably determined but which cannot be distinguished all at once by countably many choices. We structurally characterise the graphs whose directions can be distinguished all at once by countably many choices, and we structurally characterise the graphs which admit no such countably many choices. Our characterisations are phrased in terms of normal trees and tree-decompositions. Our four (sub)structural characterisations imply combinatorial characterisations of the four classes of infinite graphs that are defined by the first and second axiom of countability applied to their end spaces: the two classes of graphs whose end spaces are first countable or second countable, respectively, and the complements of these two classes.
Schmidt characterised the class of rayless graphs by an ordinal rank function, which makes it possible to prove statements about rayless graphs by transfinite induction. Halin asked whether Schmidt's rank function can be generalised to characterise other important classes of graphs. We answer Halin's question in the affirmative. Another largely open problem raised by Halin asks for a characterisation of the class of graphs with an end-faithful spanning tree. A well-studied subclass is formed by the graphs with a normal spanning tree. We determine a larger subclass, the class of normally traceable graphs, which consists of the connected graphs with a rayless tree-decomposition into normally spanned parts. Investigating the class of normally traceable graphs further we prove that, for every normally traceable graph, having a rayless spanning tree is equivalent to all its ends being dominated. Our proofs rely on a characterisation of the class of normally traceable graphs by an ordinal rank function that we provide.
In a series of four papers we determine structures whose existence is dual, in the sense of complementary, to the existence of stars or combs. Here, in the second paper of the series, we present duality theorems for combinations of stars and combs: dominating stars and dominated combs. As dominating stars exist if and only if dominated combs do, the structures complementary to them coincide. Like for arbitrary stars and combs, our duality theorems for dominated combs (and dominating stars) are phrased in terms of normal trees or tree-decompositions. The complementary structures we provide for dominated combs unify those for stars and combs and allow us to derive our duality theorems for stars and combs from those for dominated combs. This is surprising given that our complementary structures for stars and combs are quite different: those for stars are locally finite whereas those for combs are rayless.
In a series of four papers we determine structures whose existence is dual, in the sense of complementary, to the existence of stars or combs. Here, in the third paper of the series, we present duality theorems for a combination of stars and combs: undominated combs. We describe their complementary structures in terms of rayless trees and of tree-decompositions. Applications include a complete characterisation, in terms of normal spanning trees, of the graphs whose rays are dominated but which have no rayless spanning tree. Only two such graphs had so far been constructed, by Seymour and Thomas and by Thomassen. As a corollary, we show that graphs with a normal spanning tree have a rayless spanning tree if and only if all their rays are dominated.
In a series of four papers we determine structures whose existence is dual, in the sense of complementary, to the existence of stars or combs. In the first paper of our series we determined structures that are complementary to arbitrary stars or combs. Stars and combs can be combined, positively as well as negatively. In the second and third paper of our series we provided duality theorems for all but one of the possible combinations. In this fourth and final paper of our series, we complete our solution to the problem of finding complementary structures for stars, combs, and their combinations, by presenting duality theorems for the missing piece: for undominating stars. Our duality theorems are phrased in terms of end-compactified subgraphs, tree-decompositions and tangle-distinguishing separators.
We show that every infinitely edge-connected graph contains the Farey graph or $T_{\aleph_0}\!\ast t$ as a minor. These two graphs are unique with this property up to minor-equivalence.
We construct a countable planar graph which, for any two vertices $u,v$ and any integer $k\ge 1$, contains $k$ edge-disjoint order-compatible $u$--$v$ paths but not infinitely many. This graph has applications in Ramsey theory, in the study of connectivity and in the characterisation of the Farey graph.