29 citations · 334 across the 88 of their papers we have counts for
9 papers · 2 filters
Rainbow paths and large rainbow matchings
Ron Aharoni, Eli Berger, Maria Chudnovsky +1
A conjecture of the first two authors is that matchings of size in any graph have a rainbow matching of size . We prove a lower bound of , improving on…
A note on simplicial cliques
Maria Chudnovsky, Alex Scott, Paul Seymour +1
Motivated by an application in condensed matter physics and quantum information theory, we prove that every non-null even-hole-free claw-free graph has a simplicial clique, that is…
Induced subgraphs and tree decompositions I. Even-hole-free graphs of bounded degree
Tara Abrishami, Maria Chudnovsky, Kristina Vušković
Treewidth is a parameter that emerged from the study of minor closed classes of graphs (i.e. classes closed under vertex and edge deletion, and edge contraction). It in some sense…
Holes with hats and Erdős-Hajnal
Maria Chudnovsky, Paul Seymour
A "hole-with-hat" in a graph is an induced subgraph of that consists of a cycle of length at least four, together with one further vertex that has exactly two neighbours in…
List-three-coloring -free graphs with no induced 1-subdivision of
Maria Chudnovsky, Sophie Spirkl, Mingxian Zhong
Let and be positive integers. We use to denote the path with vertices and to denote the complete bipartite graph with parts of size and respecti…
Graphs with polynomially many minimal separators
Tara Abrishami, Maria Chudnovsky, Cemil Dibek +3
We show that graphs that do not contain a theta, pyramid, prism, or turtle as an induced subgraph have polynomially many minimal separators. This result is the best possible in the…