Enumeration of some families of chordal graphs

A graph is chordal if it has no induced cycle of length greater than 3. Alternatively, Dirac proved that a graph is chordal if and only if every minimal separator is a clique. From this characterization it is not hard to prove that a \(k\)-connected chordal graph can be uniquely decomposed into \((k+1)\)-connected components by cutting through all of its \(k\)-separators. One can then use the symbolic method to obtain recursive equations for the enumeration of some classes of chordal graphs. For instance, chordal maps and (labeled) chordal planar graphs can be studied starting with their 3-connected components and the proceeding to the 2-connected and connected levels. The asymptotic growth of the family can be then deduced from the equations. We also count (labeled) chordal graphs with bounded tree-width by introducing variables that keep track of the number of cliques of every size. Finally, we extend Pólya theory and the method of cycle pointing to enumerate unlabelled chordal graphs with bounded tree-width, and the same technique works for unlabelled chordal planar graphs.