Transducing paths in graph classes with unbounded shrubdepth

DOI10.1016/j.ejc.2022.103660MaRDI QIDQ6614398

Michał Pilipczuk, Sebastian Siebertz, Patrice Ossona de Mendez

Publication date: 7 October 2024

Published in: European Journal of Combinatorics (Search for Journal in Brave)

zbMATH Keywords

monadic second-order logicincidence structurestransductionsfinite relational structuresguarded second-order logic

Mathematics Subject Classification ID

Trees (05C05) Decidability of theories and sets of sentences (03B25) Higher-order logic (03B16)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sparsity. Graphs, structures, and algorithms
• Partitions of graphs into cographs
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• Complement reducible graphs
• Bi-complement reducible graphs
• Obstructions for bounded shrub-depth and rank-depth
• Classes of graphs with low complexity: the case of classes with bounded linear rankwidth
• Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs
• When Trees Grow Low: Shrubs and Fast MSO1
• On the Monadic Second-Order Transduction Hierarchy
• A note on the Erdős-Hajnal property for stable graphs
• A New Perspective on FO Model Checking of Dense Graph Classes
• The Ramsey number R(3, t) has order of magnitude t²/log t
• Twin-width I: Tractable FO Model Checking
• First-Order Interpretations of Bounded Expansion Classes
• Regularity lemmas for stable graphs
• Structural Properties of the First-Order Transduction Quasiorder

This page was built for publication: Transducing paths in graph classes with unbounded shrubdepth