Graph parameters that are coarsely equivalent to path-length

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 $\mathcal{T}(G)$ of a graph $G$ is the largest diameter of a bag in $\mathcal{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 $\mathcal{P}(G)$ of a graph $G$ is the largest diameter of a bag in $\mathcal{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\ge 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\ge 0$; (d) $G$ has a $k^{\prime }$-dominating pair with small $k^{\prime }\ge 0$; (e) some power $G^{\hat{I}}¼$ of $G$ is an AT-free (or even a cocomparability) graph for a small integer $\hat{I}¼\ge 0$.

22 pages, 3 figures