On the number of labeled graphs of bounded treewidth

Let be Tnk the number of labeled graphs on vertices and treewidth at most (equivalently, the number o<f labeled partial -trees). We show that [...] for k>1 and some explicit absolute constant c>0. Disregarding terms depending only on k, the gap between the lower and upper bound is of order (log k)n. The upper bound is a direct consequence of the well-known formula for the number of labeled lambda-trees, while the lower bound is obtained from an explicit construction. It follows from this construction that both bounds also apply to graphs of pathwidth and proper-pathwidth at most k .
Postprint (published version)