115 citations · 430 across the 53 of their papers we have counts for
13 papers · 1 filter
Twin-width II: small classes
Édouard Bonnet, Colin Geniet, Eun Jung Kim +2
The twin-width of a graph is the minimum integer such that has a -contraction sequence, that is, a sequence of iterated vertex identifications for which t…
(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…
Maximum independent sets in (pyramid, even hole)-free graphs
Maria Chudnovsky, Stéphan Thomassé, Nicolas Trotignon +1
A \emph{hole} in a graph is an induced cycle with at least 4 vertices. A graph is \emph{even-hole-free} if it does not contain a hole on an even number of vertices. A \emph{pyramid…
On the Maximum Weight Independent Set Problem in graphs without induced cycles of length at least five
Maria Chudnovsky, Marcin Pilipczuk, Michał Pilipczuk +1
A hole in a graph is an induced cycle of length at least , and an antihole is the complement of an induced cycle of length at least . A hole or antihole is long if its length…
Graphs with large chromatic number induce -cycles
Marthe Bonamy, Pierre Charbit, Stéphan Thomassé
Answering a question of Kalai and Meshulam, we prove that graphs without induced cycles of length have bounded chromatic number. This implies the very first case of a much bro…
The Erdős-Hajnal Conjecture for Long Holes and Anti-holes
Marthe Bonamy, Nicolas Bousquet, Stéphan Thomassé
Erdős and Hajnal conjectured that, for every graph , there exists a constant such that every graph on vertices which does not contain any induced copy of has a…