2025/03/07 by Dragan, Feodor F., Köhler, Ekkehard · 2 citations
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2503.05661
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 tl(G) of G is the minimum of the length, over all tree-decompositions of G. Similarly, the length of a path-decomposition \cal P(G) of a graph G is the largest diameter of a bag in \cal P(G), and the path-length pl(G) of G is the minimum of the length, over all path-decompositions of G. In this paper, we present several graph parameters that are coarsely equivalent to path-length. Among other results, we show that the path-length of a graph G is small if and only if one of the following equivalent conditions is true: (a) G can be embedded to an unweighted caterpillar tree (equivalently, to a graph of path-width one) with a small additive distortion; (b) there is a constant r≥ 0 such that for every triple of vertices u,v,w of G, disk of radius r centered at one of them intercepts all paths connecting two others; (c) G has a k-dominating shortest path with small k≥ 0; (d) G has a k'-dominating pair with small k'≥ 0; (e) some power Gμ of G is an AT-free (or even a cocomparability) graph for a small integer μ≥ 0.