8 papers · 1 filter
On Detecting -Induced Minors for Small
Tala Eagling-Vose, Barnaby Martin, Daniël Paulusma +1
We consider the -Induced Minor problem: for a fixed graph~, decide whether a given graph contains as an induced minor. While the problem is known to be NP-complete fo…
Tree independence number III. Thetas, prisms and stars
Maria Chudnovsky, Sepehr Hajebi, Nicolas Trotignon
We prove that for every , there exists such that every (theta, prism, )-free graph has tree independence number at most (whe…
On treewidth and maximum cliques
Maria Chudnovsky, Nicolas Trotignon
We construct classes of graphs that are variants of the so-called layered wheel. One of their key properties is that while the treewidth is bounded by a function of the clique numb…
Lollipops, dense cycles and chords
ZdenÄk DvoÅák, Beatriz Martins, Stéphan Thomassé +1
In 1980, Gupta, Kahn and Robertson proved that every graph with minimum degree at least contains a cycle containing at least vertices each having at least $…
Pathographs and some (un)decidability results
Daniel Carter, Nicolas Trotignon
We introduce pathographs as a framework to study graph classes defined by forbidden structures, including forbidding induced subgraphs, minors, etc. Pathographs approximately gener…
Every Graph is Essential to Large Treewidth
Bogdan Alecu, Ãdouard Bonnet, Pedro Bureo Villafana +1
We show that for every graph , there is a hereditary weakly sparse graph class of unbounded treewidth such that the -free (i.e., excluding as an induced su…