5 papers · 1 filter
On coarse tree decompositions and coarse balanced separators
Tara Abrishami, Jadwiga Czyżewska, Kacper Kluk +3
It is known that there is a linear dependence between the treewidth of a graph and its balanced separator number: the smallest integer such that for every weighing of the verti…
Burling graphs in graphs with large chromatic number
Tara Abrishami, Marcin BriaÅski, James Davies +4
A graph class is -bounded if the only way to force large chromatic number in graphs from the class is by forming a large clique. In the 1970s, ErdÅs conjectured that intersect…
Induced subgraphs and tree decompositions X. Towards logarithmic treewidth for even-hole-free graphs
Tara Abrishami, Bogdan Alecu, Maria Chudnovsky +2
A generalized -pyramid is a graph obtained from a certain kind of tree (a subdivided star or a subdivided cubic caterpillar) and the line graph of a subdivided cubic caterpillar…
Induced subgraphs and tree decompositions IX. Grid theorem for perforated graphs
Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi +1
The celebrated ErdÅs-Pósa Theorem, in one formulation, asserts that for every , graphs with no subgraph (or equivalently, minor) isomorphic to the disjoint union of …
Excluding a clique or a biclique in graphs of bounded induced matching treewidth
Tara Abrishami, Marcin BriaÅski, Jadwiga Czyżewska +4
For a tree decomposition of a graph , let denote the maximum size of an induced matching in with the property that some bag of …