8 citations · 11 across the 16 of their papers we have counts for
Showing 2022Show all
3 papers · 1 filter
cs.LO2022
First Order Logic and Twin-Width in Tournaments and Dense Oriented Graphs
Colin Geniet, Stéphan Thomassé
We characterise the classes of tournaments with tractable first-order model checking. For every hereditary class of tournaments , first-order model checking is either f…
math.CO2022★ 8 cited
Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
Marthe Bonamy, Édouard Bonnet, Hugues Déprés +5
A graph is -free if it does not contain pairwise vertex-disjoint and non-adjacent cycles. We prove that "sparse" (here, not containing large complete bipartite g…
math.GR2022
Twin-width VII: groups
Édouard Bonnet, Colin Geniet, Romain Tessera +1
Twin-width is a recently introduced graph parameter with applications in algorithmics, combinatorics, and finite model theory. For graphs of bounded degree, finiteness of twin-widt…