4 papers · 1 filter
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…