Abstract:
Given t \ge 2 and 0 \le k \le t, we prove that the number of labelled k-connected chordal graphs
with n vertices and tree-width at most t is asymptotically cn^{-5/2} \gamma^n n!, as n ? 8, for some
constants c, \gamma > 0 depending on t and k. Additionally, we show that the number of i-cliques
(2 \le i \le t) in a uniform random k-connected chordal graph with tree-width at most t is normally
distributed as n \to\infty.
The asymptotic enumeration of graphs of tree-width at most t is wide open for t \ge 3. To
the best of our knowledge, this is the first non-trivial class of graphs with bounded tree-width
where the asymptotic counting problem is solved.
This is joint work with J. Castelli, M. Noy and C. Requile
Chordal graphs with bounded tree-width
09.05.2023 15:15 - 16:45