Departmental Colloquium
Maria Chudnovsky
Princeton
Forbidding induced subgraphs: structure and algorithms
Abstract: Tree decompositions are a powerful tool in both structural
graph theory and graph algorithms. Many hard problems become tractable if
the input graph is known to have a tree decomposition of bounded
“width”. Exhibiting a particular kind of a tree decomposition is also
a useful way to describe the structure of a graph.
Tree decompositions have traditionally been used in the context of forbidden
graph minors; studying them in connection with graph containment relations of
more local flavor (such as induced subgraph or induced minors) is a relatively
new research direction. In this talk we will discuss recent progress in this
area, touching on both the classical notion of bounded tree-width, and
concepts of more structural nature.
There will be a Colloquium dinner at 7:30 p.m. in river north (place to be announced). Please email schapos@uic.edu if you want to join.
Friday September 20, 2024 at 3:00 PM in 636 SEO