Bounded-diameter tree-decompositions
type: Item
instance of: scholarly article
title: Bounded-diameter tree-decompositions
author: Eli Berger
author: Paul Seymour
published in: Combinatorica
publication date: 2024-05-31T00:00:00Z
review text: This article addresses tree decompositions and five graph invariants. A ``tree decomposition'' of a graph \(G\) is a covering \((B_t : t \in V(T))\) of \(V(G)\) where \(T\) is a tree such that for every edge \(uv \in E(G)\), there exists \(t \in V(T)\) with \(u, v \in B_t\), and such that for every path \(p\) in \(T\) with initial endpoints \(s, t \in V(T)\), if \(u\) is a vertex of \(p\) then \(B_s \cap B_t \subseteq B_u\). These sets \(B_t\) are called ``bags'', and the authors ask how small the diameter of these bags can be, as induced graphs (``inner diameter width'' or idw) or using the edge distances from \(G\)'s edge relation \(E(G)\) (``outer diameter width'' or odw).\par Meanwhile, for a graph \(G\), a tree \(T\) and a map \(\phi : V(G) \to V(T)\), the ``additive distortion'' (ad) of \(\phi\) is \(\max_{u,v} \vert d_G(u, v) - d_T(\phi(u), \phi(v))\vert \), where \(d_G\) and \(d_T\) are the edge-distance metrics on \(G\) and \(T\), respectively. And the ``McCarty-width'' (mcw) of a graph \(G\) is the least \(k\) such that for any vertices \(u, v, w \in V(G)\), there exists vertex \(x\) such that if the ball of radius \(k\) around \(x\) is removed from \(G\), no two of \(u\), \(v\), \(w\) are in the same component (if not themselves removed). Finally, for a cycle \(C\) in a graph \(G\) and a ``load'' \(F \subseteq E(C)\), say that \((C, F)\) is ``geodesic'' if, for every \(u, v \in V(C)\), \(d_G(u, v)\) is greater or equal to the minimal number of edges in \(F\) in either path from \(u\) to \(v\) in \(C\); let the ``geodesic loaded cycle'' number (glc) be the maximum of all cardinalities of loads of geodesic pairs \((C, F)\), \(C\) a cycle in \(G\).\par It turns out that for any of two of these invariants, idw, odw, glc, ad, and mcw, if we called our two chosen invariants inv1 and inv2, there exist positive constants \(A\) and \(B\) such that for all graphs \(G\), inv1\((G)/A - B \leq\) inv2\((G) \leq A\)inv2\((G) + B\). In particular, for any family of graph…
reviewed by: Gregory Loren McColm
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C62
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C78
zbMATH DE Number: 7857947
zbMATH Keywords: additive distortion
zbMATH Keywords: diameter-width
zbMATH Keywords: geodesic
zbMATH Keywords: quasi-isometry
zbMATH Keywords: tree-decomposition
zbMATH Keywords: tree-length
zbMATH Keywords: tree-width
MaRDI profile type: Publication
cites work: Acylindrical group actions on quasi-trees
cites work: Constructing group actions on quasi-trees and applications to mapping class groups
cites work: Polynomial Bounds for the Grid-Minor Theorem
cites work: Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs
cites work: Towards tight(er) bounds for the excluded grid theorem
cites work: Connected tree-width
cites work: Tree-decompositions with bags of small diameter
cites work: Tree approximation in quasi-trees
cites work: Additive Tree Spanners
cites work: Geometry of pseudocharacters.
cites work: Graph minors. V. Excluding a planar graph
cites work: Tree-chromatic number
DOI: 10.1007/S00493-024-00088-1
description: scientific article; zbMATH DE number 7857947