9 papers
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…
On the structure of (, , )-free graphs
Chính T. Hoàng, Ramin Javadi, Nicolas Trotignon
Determining the complexity of colouring ()-free graph is a long open problem. Recently Penev showed that there is a polynomial-time algorithm to colour a ($4K_1, C_4, C_…
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…
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 (where…
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…