Abstract:
Tree-width and path-width are graph parameters that play a main role in structural graph theory and complexity theory. After a gentle introduction to tree-width and path-width, we will show how to count graphs of path-width 2.
Graphs of path-width 1 are forests of caterpillars, and they are easy to count.
Graphs of tree-width 2 are series-parallel graphs, and they have been counted too.
Thus path-width 2 is a natural step in this direction, while tree-width 3 is still open.
Our solution involves meromorphic generating functions and allows us to analyze several parameters of the corresponding class of random graphs under the uniform distribution.
This is joint work with Juanjo Rué and Dimitrios Thilikos.
Counting labelled graphs of path-width 2
15.10.2019 15:15 - 16:45
Organiser:
M. Drmota
Location: