Matemática Israelo-americana que desenvolve investigação em teoria dos grafos e otimização combinatória. As contribuições de Maria Chudnovsky para a teoria dos grafos incluem a prova do teorema do grafo perfeito forte (com Neil Robertson, Paul Seymour e Robin Thomas) caracterizando os grafos perfeitos como sendo exatamente os grafos sem ciclos induzidos ímpares de comprimento pelo menos 5 ou os seus complementos. Outras contribuições incluem a coautoria do primeiro algoritmo de tempo polinomial para o reconhecimento de grafos perfeitos (tempo limitado por um polinómio de grau 9) e de uma caracterização estrutural dos grafos livres-de-garras. Em 2004, Maria Chudnovsky foi nomeada uma das “10 brilhantes” pela revista Popular Science. O seu trabalho sobre o teorema do grafo perfeito forte permitiu-lhe ganhar (e aos seus coautores) o Prémio Fulkerson em 2009. Em 2012, recebeu o prémio “genius” do Programa MacArthur Fellows.
ENSPM 2021 Presentation
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.