Treelike decompositions for transductions of sparse graphs

DOI10.1145/3531130.3533349MaRDI QIDQ6649461

Szymon Toruńczyk, Jakub Gajarský, Jan Dreier, Sandra Kiefer, Michał Pilipczuk

Publication date: 6 December 2024

zbMATH Keywords

nowhere densetransductionbounded expansionshrubdepth

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Model theory of finite structures (03C13) Density (toughness, etc.) (05C42)

Cites Work

• Unnamed Item
• Sparsity. Graphs, structures, and algorithms
• Colouring graphs with bounded generalized colouring number
• Polynomial bounds for centered colorings on proper minor-closed graph classes
• Clustering powers of sparse graphs
• Uniform orderings for generalized coloring numbers
• A combinatorial problem; stability and order for models and theories in infinitary languages
• On the density of families of sets
• A New Perspective on FO Model Checking of Dense Graph Classes
• Deciding First-Order Properties of Nowhere Dense Graphs
• Twin-width II: small classes
• Twin-width I: Tractable FO Model Checking
• First-Order Interpretations of Bounded Expansion Classes
• On the number of types in sparse graphs
• Linear rankwidth meets stability
• Testing first-order properties for subclasses of sparse graphs
• Erdös--Hajnal Properties for Powers of Sparse Graphs

This page was built for publication: Treelike decompositions for transductions of sparse graphs