From the 2 of 12 linked papers with an AI index.
12 papers
Excluding paths and bicliques
Maria Chudnovsky, Julien Codsi, Matjaž Krnc +1
The paper improves the known Ramsey‑type bound on the maximum length of a path in graphs that exclude a fixed path and a biclique as induced subgraphs, showing it can be taken sing…
Induced-Minor-Closed Classes have Linear, Square-Root, or Sub-Polynomial Tree-Independence
Maria Chudnovsky, Julien Codsi, Ajaykrishnan E S +1
The paper shows that any graph either contains a large complete bipartite graph or a large wall as an induced minor, or else its tree‑independence number grows sub‑polynomially, le…
Coarse Balanced Separators in Biclique-Induced-Minor-Free Graphs
Maria Chudnovsky, Julien Codsi, Claire Kaneshiro
It is a classical theorem of Robertson and Seymour (1986) that the treewidth of a graph is linearly related to its separation number: the smallest integer such that, for every…
Induced Minors and Coarse Tree Decompositions
Maria Chudnovsky, Julien Codsi, Ajaykrishnan E S +1
Let be a graph, be a vertex set in and be a positive integer. The distance -independence number of is the size of the largest subset $I \subse…
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…
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…