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…
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…
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 $…
Treewidth versus clique number: induced minors
Claire Hilaire, Martin Milanič, Nicolas Trotignon +1
We prove that a hereditary class of graphs is -bounded if and only if the induced minors of the graphs from the class form a -bounded class.
A structural description of Zykov and Blanche Descartes graphs
Malory Marin, Stéphan Thomassé, Nicolas Trotignon +1
In 1949, Zykov proposed the first explicit construction of triangle-free graphs with arbitrarily large chromatic number. We define a Zykov graph as any induced subgraph of a graph…