56 citations · 715 across the 68 of their papers we have counts for
4 papers · 1 filter
On the tree-width of even-hole-free graphs
Pierre Aboulker, Isolde Adler, Eun Jung Kim +2
The class of all even-hole-free graphs has unbounded tree-width, as it contains all complete graphs. Recently, a class of (even-hole, )-free graphs was constructed, that still…
A class of graphs with large rankwidth
Chính Hoàng, Nicolas Trotignon
We describe several graphs with arbitrarily large rankwidth (or equivalently with arbitrarily large cliquewidth). Korpelainen, Lozin, and Mayhill [Split permutation graphs, Graphs…
Graphs with polynomially many minimal separators
Tara Abrishami, Maria Chudnovsky, Cemil Dibek +3
We show that graphs that do not contain a theta, pyramid, prism, or turtle as an induced subgraph have polynomially many minimal separators. This result is the best possible in the…
(Theta, triangle)-free and (even hole, )-free graphs. Part 2 : bounds on treewidth
Marcin Pilipczuk, Ni Luh Dewi Sintiari, Stéphan Thomassé +1
A {\em theta} is a graph made of three internally vertex-disjoint chordless paths , , of length at least~2 and such that no edge…