1 citations · 1 across the 8 of their papers we have counts for
4 papers · 1 filter
Twin-width III: Max Independent Set, Min Dominating Set, and Coloring
Édouard Bonnet, Colin Geniet, Eun Jung Kim +2
We recently introduced the graph invariant twin-width, and showed that first-order model checking can be solved in time for -vertex graphs given with a witness that th…
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…
An algorithmic weakening of the Erdős-Hajnal conjecture
Édouard Bonnet, Stéphan Thomassé, Xuan Thang Tran +1
We study the approximability of the Maximum Independent Set (MIS) problem in -free graphs (that is, graphs which do not admit as an induced subgraph). As one motivation we i…
Twin-width I: tractable FO model checking
Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé +1
Inspired by a width invariant defined on permutations by Guillemot and Marx [SODA '14], we introduce the notion of twin-width on graphs and on matrices. Proper minor-closed classes…