29 papers
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…
On the chromatic number of the union of comparability graphs
Maria Chudnovsky, Wouter Cames van Batenburg, 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 and , there is a graph with cliq…
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…
(Treewidth, Clique)-Boundedness and Poly-logarithmic Tree-Independence
Maria Chudnovsky, Ajaykrishnan E S, Daniel Lokshtanov
An independent set in a graph is a set of pairwise non-adjacent vertices. A tree decomposition of is a pair where is a tree and $Ï: V(T) \rightarrow 2^{V(G)}…
Tree-independence number and forbidden induced subgraphs: excluding a -vertex path and a -biclique
Maria Chudnovsky, Julien Codsi, J. Pascal Gollin +2
We show that for every positive integer there exists an integer such that every graph that contains no induced subgraph isomorphic to either the -vertex path or…
Minors of plane digraphs
Maria Chudnovsky, Paul Seymour
A digraph is a ``semi-strong minor'' of another, , if a subdivision of can be obtained from a subdigraph of by contracting strongly-connected subdigraphs to single v…