Two Treewidth Problems
Michael Pelsmajer
Department of Applied Mathematics
Illinois Institute of Technology
Treewidth is, in a way, a measure of how closely a graph resembles a tree. It is important for both applied and theoretical reasons (e.g., dynamic programming, fixed-parameter tractability, graph minors project).
In this talk we introduce treewidth and describe two research questions that should be accessible to students. One concerns a graph coloring variant called "equitable list coloring", and the other generalizes independent sets and induced matchings.