3 papers
math.CO2023
Sparse Graphs of Twin-width 2 Have Bounded Tree-width
Benjamin Bergougnoux, Jakub Gajarský, Grzegorz Guśpiel +3
Twin-width is a structural width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS 2020]. Very briefly, its essence is a gradual reduction (a contraction sequence)…
cs.LO2023
Flipper games for monadically stable graph classes
Jakub Gajarský, Nikolas Mählmann, Rose McCarty +6
A class of graphs is monadically stable if for any unary expansion of , one cannot interpret, in first-order logic, arbitrarily l…
cs.LO2022
Twin-width and types
Jakub Gajarský, Michał Pilipczuk, Wojciech Przybyszewski +1
We study problems connected to first-order logic in graphs of bounded twin-width. Inspired by the approach of Bonnet et al. [FOCS 2020], we introduce a robust methodology of local…