Maria Chudnovsky

Induced subgraphs of bounded treewidth and the container method

Society for Industrial and Applied Mathematics eBooks · 2021 · 22 citations

A hole in a graph is an induced cycle of length at least 4. A hole is long if its length is at least 5. By Pt we denote a path on t vertices. In this paper we give polynomial-time algorithms for the following problems: the Maximum Weight Independent Set problem in long-hole-free graphs, and the Feedback Vertex Set problem in P5-free graphs. Each of the above results resolves a corresponding long-standing open problem. An extended C5 is a five-vertex hole with an additional vertex adjacent to one…

Cooperative colorings of trees and of bipartite graphs

The Electronic Journal of Combinatorics · 2020 · 4 citations

International audience

Reuniting χ-boundedness with polynomial χ-boundedness

Journal of Combinatorial Theory Series B · 2025-08-28 · 2 citations

Tree independence number II. Three-path-configurations

Journal of Combinatorial Theory Series B · 2025-09-08 · 1 citations

On prime Cayley graphs

Journal of Combinatorics · 2026-01-01

The decomposition of complex networks into smaller, interconnected components is a central challenge in network theory with a wide range of potential applications. In this paper, we utilize tools from group theory and ring theory to study this problem when the network is a Cayley graph. In particular, we answer the following question: Which Cayley graphs are prime?