Pablo Blanco, Rutgers University

Abstract

I'll be talking about tree decompositions and their relation to spanning trees. A tree decomposition is a way to represent a graph as a tree; generally, a good tree decomposition is one with small "tree-width" and this tells you how much your graph looks like a tree.  Courcelle's Theorem tells us that (many of) the properties of graphs with bounded tree-width are quickly checked.

See: https://sites.math.rutgers.edu/~kmg326/GCS/GCS.html