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…
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 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_…
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…