ENSPM 2021 Talk
Title: Induced subgraphs and tree decompositions
Abstract: Tree decompositions are a powerful tool in structural graph theory, that is traditionally used in the context of forbidden graph minors. Connecting tree decompositions and forbidden induced subgraphs has so far remained out of reach. Recently we obtained several results in this direction; the talk will be a survey of these results.
Maria Chudnovsky (Princeton University, USA)
Israeli-American mathematician working on graph theory and combinatorial optimization. Chudnovsky’s contributions to graph theory include the proof of the strong perfect graph theorem (with Neil Robertson, Paul Seymour, and Robin Thomas) characterizing perfect graphs as being exactly the graphs with no odd induced cycles of length at least 5 or their complements. Other research contributions of Chudnovsky include co-authorship of the first polynomial-time algorithm for recognizing perfect graphs (time bounded by a polynomial of degree 9), and of a structural characterization of the claw-free graphs. In 2004 Chudnovsky was named one of the “Brilliant 10” by Popular Science magazine. Her work on the strong perfect graph theorem won for her and her co-authors the 2009 Fulkerson Prize. In 2012 she was awarded a “genius award” under the MacArthur Fellows Program.
More info >
