8 citations · 11 across the 16 of their papers we have counts for
7 papers · 1 filter
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…
Moderately beyond clique-width: reduced component max-leaf and related parameters
Édouard Bonnet, Yeonsu Chang, Julien Duron +2
Reduced parameters [BKW, JCTB '26; BKRT, SODA '22] are defined via contraction sequences. Based on this framework, we introduce the reduced component max-leaf, denoted by $\operato…
Variants of Merge-Width and Applications
Karolina Drabik, Maël Dumas, Colin Geniet +3
Merge-width is a recently introduced family of graph parameters that unifies treewidth, clique-width, twin-width, and generalised colouring numbers. We prove the equivalence of sev…
Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions
Colin Geniet, Aliénor Goubault-Larrecq, Kévin Perrot
We present a Rice-like complexity lower bound for any MSO-definable problem on binary structures succinctly encoded by circuits. This work extends the framework recently developed…
Fast Shortest Path in Graphs With Sparse Signed Tree Models and Applications
Édouard Bonnet, Colin Geniet, Eun Jung Kim +1
A signed tree model of a graph is a compact binary structure consisting of a rooted binary tree whose leaves are bijectively mapped to the vertices of , together with 2-colo…
Basis Number of Graphs Excluding Minors
Colin Geniet, Ugo Giocanti
The basis number of a graph is the minimum such that the cycle space of is generated by a family of cycles using each edge at most times. A classical result of Mac…
Transducing Linear Decompositions of Tournaments
Colin Geniet, Fatemeh Ghasemi, Mamadou Moustapha Kanté
Bojańczyk, Pilipczuk, and Grohe [LICS '18] proved that for graphs of bounded linear clique-width, clique-decompositions of bounded width can be produced by a CMSO transduction. We…