Graphs and Matroids Seminar - Catherine Greenhill

Title: Approximately counting independent sets in graphs with bounded bipartite pathwidth

Abstract:

In 1989, Jerrum and Sinclair showed that a natural Markov chain for counting
matchings in a given graph G is rapidly mixing. This chain can equivalently
be viewed as counting independent sets in line graphs. We generalise their
approach to the class of all graphs with the following property: every bipartite
induced subgraph of G has pathwidth at most p. Here p is a positive integer
and the mixing time of the Markov chain will depend on p.
We also describe two classes of graphs (described in terms of forbidden induced
subgraphs) that satisfy this condition. Both of these classes generalise the class
of claw-free graphs.