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 cs.DMShow all

3 papers · 1 filter

cs.DM2026

Reducing CMSO to Unbreakable Graphs Cannot be Computable

Colin Geniet, Roohani Sharma

Lokshtanov, Ramanujan, Saurabh, and Zehavi [ICALP 2018] proved that for any CMSO formula , testing on arbitrary graphs can be reduced to testing it on -unbreakable gr…

cs.DM2025

First-Order Logic and Twin-Width for Some Geometric Graphs

Colin Geniet, Gunwoo Kim, Lucas Meijer

For some geometric graph classes, tractability of testing first-order formulas is precisely characterised by the graph parameter twin-width. This was first proved for interval grap…

cs.DM2020

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…