19 citations · 43 across the 33 of their papers we have counts for
13 papers · 1 filter
Induced subgraphs and tree decompositions XVIII. Obstructions to bounded pathwidth
Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl
The pathwidth of a graph is the smallest such that can be constructed from a sequence of graphs, each on at most vertices, by gluing them together i…
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…
Sparse induced subgraphs in -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…
Induced subgraphs and tree decompositions XVII. Anticomplete sets of large treewidth
Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl
Two sets of vertices in a graph are "anticomplete" if and there is no edge in with an end in and an end in . We prove that every graph $…
Induced subgraphs and tree decompositions XVI. Complete bipartite induced minors
Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl
We prove that for every graph with a sufficiently large complete bipartite induced minor, either has an induced minor isomorphic to a large wall, or contains a large co…
Tree Independence Number IV. Even-hole-free Graphs
Maria Chudnovsky, Peter Gartland, Sepehr Hajebi +2
We prove that the tree independence number of every even-hole-free graph is at most polylogarithmic in its number of vertices. More explicitly, we prove that there exists a constan…
Counting independent sets in structured graphs
Matija Bucić, Maria Chudnovsky, Julien Codsi
Counting independent sets in graphs and hypergraphs under a variety of restrictions is a classical question with a long history. It is the subject of the celebrated container metho…
Tree independence number III. Thetas, prisms and stars
Maria Chudnovsky, Sepehr Hajebi, Nicolas Trotignon
We prove that for every , there exists such that every (theta, prism, )-free graph has tree independence number at most (where…
On treewidth and maximum cliques
Maria Chudnovsky, Nicolas Trotignon
We construct classes of graphs that are variants of the so-called layered wheel. One of their key properties is that while the treewidth is bounded by a function of the clique numb…
Unavoidable induced subgraphs in graphs with complete bipartite induced minors
Maria Chudnovsky, Meike Hatzel, Tuukka Korhonen +2
We prove that if a graph contains the complete bipartite graph as an induced minor, then it contains a cycle of length at most~12 or a theta as an induced subgraph. W…
Tree independence number II. Three-path-configurations
Maria Chudnovsky, Sepehr Hajebi, Daniel Lokshtanov +1
A three-path-configuration is a graph consisting of three pairwise internally-disjoint paths the union of every two of which is an induced cycle of length at least four. A graph is…
Induced subgraphs and tree decompositions XV. Even-hole-free graphs with bounded clique number have logarithmic treewidth
Maria Chudnovsky, Peter Gartland, Sepehr Hajebi +2
We prove that for every integer there exists an integer such that every -vertex even-hole-free graph with no clique of size has treewidth at most $c_t\…
On prime Cayley graphs
Maria Chudnovsky, Michal Cizek, Logan Crew +4
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, w…