4 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…
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 …
Parameterized Approximation of Rectangle Stabbing
Huairui Chu, Ajaykrishnan E S, Daniel Lokshtanov +4
In the Rectangle Stabbing problem, input is a set of axis-parallel rectangles and a set of axis parallel lines in the plane. The task is to find a minimum siz…
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…