Graph parameters that are coarsely equivalent to tree-length

February 02, 2025 ยท The Ethereal ยท ๐Ÿ› arXiv.org

๐Ÿ”ฎ THE ETHEREAL: The Ethereal
Pure theory โ€” exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Feodor F. Dragan arXiv ID 2502.00951 Category math.CO: Combinatorics Cross-listed cs.DS Citations 4 Venue arXiv.org Last Checked 6 months ago
Abstract
Two graph parameters are said to be coarsely equivalent if they are within constant factors from each other for every graph $G$. Recently, several graph parameters were shown to be coarsely equivalent to tree-length. Recall that the length of a tree-decomposition ${\cal T}(G)$ of a graph $G$ is the largest diameter of a bag in ${\cal T}(G)$, and the tree-length of $G$ is the minimum of the length, over all tree-decompositions of $G$. We present simpler and sometimes with better bounds proofs for those known in literature results and further extend this list of graph parameters coarsely equivalent to tree-length. Among other new results, we show that the tree-length of a graph $G$ is small if and only if for every bramble ${\cal F}$ (or every Helly family of connected subgraphs ${\cal F}$, or every Helly family of paths ${\cal F}$) of $G$, there is a disk in $G$ with small radius that intercepts all members of ${\cal F}$. Furthermore, the tree-length of a graph $G$ is small if and only if $G$ can be embedded with a small additive distortion to an unweighted tree with the same vertex set as in $G$ (not involving any Steiner points). Additionally, we introduce a new natural "bridging`` property for cycles, which generalizes a known property of cycles in chordal graphs, and show that it also coarsely defines the tree-length.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

๐Ÿ“œ Similar Papers

In the same crypt โ€” Combinatorics

๐Ÿ”ฎ ๐Ÿ”ฎ The Ethereal

Tables of subspace codes

Daniel Heinlein, Michael Kiermaier, ... (+2 more)

math.CO ๐Ÿ› arXiv ๐Ÿ“š 94 cites 10 years ago