2606.20452

Total: 1

#1 Tree-cut decompositions for displaying undominated edge-ends [PDF] [Copy] [Kimi] [REL]

Authors: Max Pitz, Lucas Real

We prove that every graph admits a linked, componental, rooted tree-cut decomposition of finite adhesion that displays all undominated edge-ends. As a first application, we deduce that this tree-cut decomposition also displays the edge-degrees of all undominated edge-ends. For locally finite graphs $-$ where every end is an undominated edge-end $-$ this yields a linked tree-cut decomposition of finite adhesion into $\textit{finite}$ parts that displays all ends and their edge-degrees. As a second application, this latter tree-cut decomposition yields short, unified deductions of Thomassen's theorem on boundary-linked finite partitions, and of Bruhn and Stein's characterisation of Eulerian locally finite graphs in terms of even ends.

Subject: Combinatorics

Publish: 2026-06-18 16:30:09 UTC