Maria Chudnovsky

activity

20132026

most citedDecomposing Berge graphs and detecting balanced skew partitions

19 citations · 43 across the 33 of their papers we have counts for

collaborators

Showing 2025Show all

13 papers · 1 filter

math.CO2025

Tree-independence number VII. Excluding a star

Maria Chudnovsky, Jadwiga Czyżewska, Marcin Pilipczuk +1

We prove that for every fixed integer $s$ and every planar graph $H$ , the class of $H$ -induced-minor-free and $K_{1, s}$ -induced-subgraph-free graphs has polylogarithmic tree-indepe…

math.CO2025

Dominated balanced separators in wheel-induced-minor-free graphs

Maria Chudnovsky, J. Pascal Gollin, Matjaž Krnc +1

Gartland and Lokshtanov conjectured that every graph that excludes some planar graph as an induced minor has a balanced separator, that is, a separator whose deletion leaves every…

math.CO2025

Localized Erdős-Pósa Property for Subdivisions

Icey Siyi Ai, Maria Chudnovsky, Julien Codsi

For a graph $H$ , we say that $H$ has the Erdős-Pósa property for subdivisions with function $f$ , if, for every nonnegative integer $k$ and every graph $G$ , either $G$ contains (as…

math.CO2025

Induced minors and subpolynomial treewidth

Maria Chudnovsky, Julien Codsi, David Fischer +1

Given a family $H$ of graphs, we say that a graph $G$ is $H$ -induced-minor-free if no induced minor of $G$ is isomorphic to a member of $H$ , We denote…

math.CO2025

(Treewidth, Clique)-Boundedness and Poly-logarithmic Tree-Independence

Maria Chudnovsky, Ajaykrishnan E S, Daniel Lokshtanov

An independent set in a graph $G$ is a set of pairwise non-adjacent vertices. A tree decomposition of $G$ is a pair $(T, χ)$ where $T$ is a tree and $χ : V (T) \to 2^{V (G)}$ …

math.CO2025

Tree-independence number VI. Thetas and pyramids

Maria Chudnovsky, Julien Codsi

Given a family $H$ of graphs, we say that a graph $G$ is $H$ -free if no induced subgraph of $G$ is isomorphic to a member of $H$ . Let $W_{t \times t}$ …

math.CO2025

String Graph Obstacles of High Girth and of Bounded Degree

Maria Chudnovsky, David Eppstein, David Fischer

A string graph is the intersection graph of curves in the plane. Kratochvíl previously showed the existence of infinitely many obstacles: graphs that are not string graphs but for…

math.CO2025

A simple layered-wheel-like construction

Maria Chudnovsky, David Fischer, Sepehr Hajebi +2

In recent years, there has been significant interest in characterizing the induced subgraph obstructions to bounded treewidth and pathwidth. While this has recently been resolved f…

math.CO2025

The vertex sets of subtrees of a tree

Maria Chudnovsky, Tung Nguyen, Alex Scott +1

Let $F$ be a set of subsets of a set $W$ . When is there a tree $T$ with vertex set $W$ such that each member of $F$ is the set of vertices of a subtree of $T$ ?…

math.CO2025

Induced subgraphs and tree decompositions XIX. Thetas and forests

Maria Chudnovsky, Julien Codsi, Sepehr Hajebi +1

Let $H$ be a graph and let $C$ be a hereditary class of theta-free graphs such that $H \in / C$ . We prove that if (a) $H$ is a forest; and (b) $C$ exc…

math.CO2025

Coarse Balanced Separators and Tree-Decompositions

Maria Chudnovsky, Robert Hickingbotham

A classical result of Robertson and Seymour (1986) states that the treewidth of a graph is linearly tied to its separation number: the smallest integer $k$ such that, for every wei…

math.CO2025

Tree independence number V. Walls and claws

Maria Chudnovsky, Julien Codsi, Daniel Lokshtanov +2

Given a family $H$ of graphs, we say that a graph $G$ is $H$ -free if no induced subgraph of $G$ is isomorphic to a member of $H$ . Let $S_{t, t, t}$ be t…

math.CO2025

Strictly Metrizable Graphs are Minor-Closed

Maria Chudnovsky, Daniel Cizma, Nati Linial

A consistent path system in a graph $G$ is an collection of paths, with exactly one path between any two vertices in $G$ . A path system is said to be consistent if it is intersecti…