Colin Geniet

activity

20202026

most citedSparse graphs with bounded induced cycle packing number have logarithmic treewidth

8 citations · 11 across the 16 of their papers we have counts for

collaborators

Showing 2020Show all

2 papers · 1 filter

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…