Let p=(v1,…,vn) be a self-avoiding walk in a graph G. Let d(p) be the number of unique i, 1≤i<n such that there's a self-avoiding walk q that starts at vn and ends at vi without visiting any other vertices in p. Let d(G) be maxp d(p) with maximum taken over all self-avoiding walks in G. Is d(G) related to treewidth of G?


Motivation: [arXiv:math/0701494](http://arxiv.org/abs/math/0701494) gives a way to represent marginal probability of a node on an arbitrary graph (ie, the probability of that node taking a particular color when we randomly pick a proper coloring of G) as the marginal probability of the root of a self-avoiding walk tree built from this graph. Finding marginal probability in this representation seems to scale exponentially in d(G), whereas finding marginal in original representation (junction tree algorithm), scales exponentially in treewidth of G.


This relates to the complexity of counting the number of colorings in a graph, because there's a computationally efficient way to get the number of colorings from marginals (sequential cavity method), so if d(G) grew slower than treewidth(G) for some family of graphs, this would give an algorithm for counting colorings that's faster than the tree-decomposition based one



Is this measure related to treewidth?
If a graph has bounded treewidth, it has $O(n)$ edges. And if it has $O(n)$ edges, it has $2^{O(n)}$ self-avoiding walks, since a self-avoiding walk can be specified as a set of edges. This is in contrast with arbitrary graphs where the number of self-avoiding walks can be exponential in $n\log n$. But it's not really a relation to treewidth since the same thing holds for any sparse graph.


