16 papers · 1 filter
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…
Induced Cycles of Many Lengths
Maria Chudnovsky, Ilya Maier
Let be a graph and let be the number of distinct induced cycle lengths in . We show that for , every graph that does not contain an in…
Tree-independence number VII. Excluding a star
Maria Chudnovsky, Jadwiga Czyżewska, Marcin Pilipczuk +1
We prove that for every fixed integer and every planar graph , the class of -induced-minor-free and -induced-subgraph-free graphs has polylogarithmic tree-indepe…
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…
Induced minors and subpolynomial treewidth
Maria Chudnovsky, Julien Codsi, David Fischer +1
Given a family of graphs, we say that a graph is -induced-minor-free if no induced minor of is isomorphic to a member of , We denote…