Maria Chudnovsky : Forbidding induced subgraphs: structure and algorithms

Posted by Laura Schaposnik , part of the Departmental Colloquium.

At

Sept. 20, 2024, 3 p.m.

In

636 SEO

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.