Résumé
We focus on counting the number of labeled graphs on$n$vertices and treewidth at most$k$(or equivalently, the number of labeled partial$k$ -trees), which we denote by$T_{n,k}$ . So far, only the particular cases$T_{n,1}$and$T_{n,2}$had been studied. We show that$$ \left(c \cdot \frac{k\cdot 2^k \cdot n}{\log k} \right)^n \cdot 2^{-\frac{k(k+3)}{2}} \cdot k^{-2k-2}\ \leq\ T_{n,k}\ \leq\ \left(k \cdot 2^k \cdot n\right)^n \cdot 2^{-\frac{k(k+1)}{2}} \cdot k^{-k}, $$for$k > 1$and some explicit absolute constant$c > 0$ . The upper bound is an immediate consequence of the well-known number of labeled$k$ -trees, while the lower bound is obtained from an explicit algorithmic construction. It follows from this construction that both bounds also apply to graphs of pathwidth and proper-pathwidth at most$k$ .