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

41 papers

math.CO2026

Finding non-bisimplicial and triad-free minimal separators

Maria Chudnovsky, Ilya Maier

A $u - v$ separator in $G$ is a set $S \subseteq V (G) ∖ {u, v}$ such that there is no $u - v$ path in $G ∖ S$ . A minimal separator in $G$ is a set $S$ such t…

cs.DS2026

Forbidden Subgraphs of Graphs with Low Bandwidth

Maria Chudnovsky, Daniel Lokshtanov, Eran Nevo

A layout of a graph G is an injective function $f : V (G) \to Z$ , and the bandwidth of a layout f is $b w (G, f) = ma x_{uv \in E (G)} ∣ f (u) - f (v) ∣$ . The bandwidth bw(G) of G is…

math.CO2026

On the chromatic number of the union of comparability graphs

Wouter Cames van Batenburg, Maria Chudnovsky, Linda Cook +3

Resolving in a strong sense a problem of Gyárfás on the union of two perfect graphs, we prove that for every pair of positive integers $d$ and $k$ , there is a graph $G$ with clique…

math.CO2026

Tree-independence number and forbidden induced subgraphs: excluding a $6$ -vertex path and a $(2, t)$ -biclique

Maria Chudnovsky, Julien Codsi, J. Pascal Gollin +2

We show that for every positive integer $t \geq 2$ there exists an integer $s$ such that every graph that contains no induced subgraph isomorphic to either the $6$ -vertex path or…

math.CO2026

Minors of plane digraphs

Maria Chudnovsky, Paul Seymour

A digraph $H$ is a ``semi-strong minor'' of another, $G$ , if a subdivision of $H$ can be obtained from a subdigraph of $G$ by contracting strongly-connected subdigraphs to single v…

math.CO2026

Induced Cycles of Many Lengths

Maria Chudnovsky, Ilya Maier

Let $G$ be a graph and let $cl (G)$ be the number of distinct induced cycle lengths in $G$ . We show that for $c, t \in N$ , every graph $G$ that does not contain an in…

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…

math.CO2024

Induced subgraphs and tree decompositions XVIII. Obstructions to bounded pathwidth

Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl

The pathwidth of a graph $G$ is the smallest $w \in N$ such that $G$ can be constructed from a sequence of graphs, each on at most $w + 1$ vertices, by gluing them together i…

math.CO2024

Colouring t-perfect graphs

Maria Chudnovsky, Linda Cook, James Davies +2

Perfect graphs can be described as the graphs whose stable set polytopes are defined by their non-negativity and clique inequalities (including edge inequalities). In 1975, Chvátal…

cs.DS2024

Sparse induced subgraphs in $P_{7}$ -free graphs of bounded clique number

Maria Chudnovsky, Jadwiga Czyżewska, Kacper Kluk +2

Many natural computational problems, including e.g. Max Weight Independent Set, Feedback Vertex Set, or Vertex Planarization, can be unified under an umbrella of finding the larges…

math.CO2024

Induced subgraphs and tree decompositions XVII. Anticomplete sets of large treewidth

Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl

Two sets $X, Y$ of vertices in a graph $G$ are "anticomplete" if $X \cap Y = \emptyset$ and there is no edge in $G$ with an end in $X$ and an end in $Y$ . We prove that every graph $…

math.CO2024★ 1 cited

Induced subgraphs and tree decompositions XVI. Complete bipartite induced minors

Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl

We prove that for every graph $G$ with a sufficiently large complete bipartite induced minor, either $G$ has an induced minor isomorphic to a large wall, or $G$ contains a large co…

Finding non-bisimplicial and triad-free minimal separators

Forbidden Subgraphs of Graphs with Low Bandwidth

On the chromatic number of the union of comparability graphs

Tree-independence number and forbidden induced subgraphs: excluding a 6-vertex path and a (2,t)-biclique

Minors of plane digraphs

Induced Cycles of Many Lengths

Tree-independence number VII. Excluding a star

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

Localized Erdős-Pósa Property for Subdivisions

Induced minors and subpolynomial treewidth

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

Tree-independence number VI. Thetas and pyramids

String Graph Obstacles of High Girth and of Bounded Degree

A simple layered-wheel-like construction

The vertex sets of subtrees of a tree

Induced subgraphs and tree decompositions XIX. Thetas and forests

Coarse Balanced Separators and Tree-Decompositions

Tree independence number V. Walls and claws

Strictly Metrizable Graphs are Minor-Closed

Induced subgraphs and tree decompositions XVIII. Obstructions to bounded pathwidth

Colouring t-perfect graphs

Sparse induced subgraphs in P7​-free graphs of bounded clique number

Induced subgraphs and tree decompositions XVII. Anticomplete sets of large treewidth

Induced subgraphs and tree decompositions XVI. Complete bipartite induced minors

Tree-independence number and forbidden induced subgraphs: excluding a $6$ -vertex path and a $(2, t)$ -biclique

Sparse induced subgraphs in $P_{7}$ -free graphs of bounded clique number