1 citations · 2 across the 13 of their papers we have counts for
13 papers · 1 filter
Tree-independence number VIII. 3PC-free graphs have logarithmic tree-independence number
Maria Chudnovsky, Julien Codsi, Ajaykrishnan E S +2
A three-path-configuration is a graph consisting of three pairwise internally vertex-disjoint paths, the union of every two of which is an induced cycle of length at least four. A…
Excluding paths and bicliques
Maria Chudnovsky, Julien Codsi, Matjaž Krnc +1
Classes of graphs excluding a path and a biclique as induced subgraphs are extensively studied in the literature. One of the key structural results for such graphs is a Ramsey-type…
Induced-Minor-Closed Classes have Linear, Square-Root, or Sub-Polynomial Tree-Independence
Maria Chudnovsky, Julien Codsi, Ajaykrishnan E S +1
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 …
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…
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 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…
Extremal Graphs for the Lights Out Problem
Julien Codsi, Sergio Cristancho, Alexander Divoux +1
Lights Out is a game played on a graph where every vertex has a light bulb that is either on or off, and pressing a vertex toggles the state of every vertex in the closed n…
Localized Erdős-Pósa Property for Subdivisions
Icey Siyi Ai, Maria Chudnovsky, Julien Codsi
For a graph , we say that has the Erdős-Pósa property for subdivisions with function , if, for every nonnegative integer and every graph , either contains (as…
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…
Tree-independence number VI. Thetas and pyramids
Maria Chudnovsky, Julien Codsi
Given a family of graphs, we say that a graph is -free if no induced subgraph of is isomorphic to a member of . Let …
Induced subgraphs and tree decompositions XIX. Thetas and forests
Maria Chudnovsky, Julien Codsi, Sepehr Hajebi +1
Let be a graph and let be a hereditary class of theta-free graphs such that . We prove that if (a) is a forest; and (b) exc…
Tree independence number V. Walls and claws
Maria Chudnovsky, Julien Codsi, Daniel Lokshtanov +2
Given a family of graphs, we say that a graph is -free if no induced subgraph of is isomorphic to a member of . Let be t…
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…