Twin-width I: Tractable FO Model Checking
From MaRDI portal
Publication:5066940
DOI10.1145/3486655OpenAlexW3216575656MaRDI QIDQ5066940
Rémi Watrigant, Eun Jung Kim, Édouard Bonnet, Steéphan Thomassé
Publication date: 31 March 2022
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2004.14789
Related Items (21)
Bounds for the Twin-Width of Graphs ⋮ Stack-number is not bounded by queue-number ⋮ Twin-width can be exponential in treewidth ⋮ Graphs of bounded twin-width are quasi-polynomially \(\chi \)-bounded ⋮ Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts ⋮ Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs ⋮ Twin-width and transductions of proper \(k\)-mixed-thin graphs ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs ⋮ Parity permutation pattern matching ⋮ Neighbourhood complexity of graphs of bounded twin-width ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes ⋮ Functionality of box intersection graphs ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ On the thinness of trees ⋮ Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs ⋮ \(\boldsymbol{(\alpha, \beta )}\)-Modules in Graphs ⋮ A meta-theorem for distributed certification ⋮ Twin-width and polynomial kernels ⋮ A meta-theorem for distributed certification
This page was built for publication: Twin-width I: Tractable FO Model Checking
