Colin Geniet

collaborators

2 papers

cs.DS2020

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 $f (d, k) n$ for $n$ -vertex graphs given with a witness that th…

cs.DM2020

Twin-width II: small classes

Édouard Bonnet, Colin Geniet, Eun Jung Kim +2

The twin-width of a graph $G$ is the minimum integer $d$ such that $G$ has a $d$ -contraction sequence, that is, a sequence of $∣ V (G) ∣ - 1$ iterated vertex identifications for which t…