Graphs and Matroids - Sophie Spirkl

Tuesday, February 13, 2024 3:00 pm - 4:00 pm EST (GMT -05:00)

Title: Odd cycle transversal in P5-free graphs

Speaker: Sophie Spirkl
Affiliation: University of Waterloo
Location: MC 5417

Abstract: Odd cycle transversal is a fun computational problem, somewhere between colouring and independent set: we are (equivalently) looking for a bipartite induced subgraph of maximum weight. As one might expect, this is NP-hard; I will tell you how to solve this problem in polynomial time in P5-free graphs (and more). Joint work with Cece Henderson, Evelyne Smith-Roberge, and Rebecca Whitman.

Note: I am COVID-cautious and will bring masks for those willing to wear them.