Graph classes through the lens of logic
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929664956563456 |
|---|---|
| author | Pilipczuk, Michał |
| author_facet | Pilipczuk, Michał |
| contents | Graph transformations definable in logic can be described using the notion of transductions. By understanding transductions as a basic embedding mechanism, which captures the possibility of encoding one graph in another graph by means of logical formulas, we obtain a new perspective on the landscape of graph classes and of their properties. The aim of this survey is to give a comprehensive presentation of this angle on structural graph theory.
We first give a logic-focused overview of classic graph-theoretic concepts, such as treedepth, shrubdepth, treewidth, cliquewidth, twin-width, bounded expansion, and nowhere denseness. Then, we present recent developments related to notions defined purely through transductions, such as monadic stability, monadic dependence, and classes of structurally sparse graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_04166 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Graph classes through the lens of logic Pilipczuk, Michał Combinatorics Discrete Mathematics Data Structures and Algorithms Logic in Computer Science Graph transformations definable in logic can be described using the notion of transductions. By understanding transductions as a basic embedding mechanism, which captures the possibility of encoding one graph in another graph by means of logical formulas, we obtain a new perspective on the landscape of graph classes and of their properties. The aim of this survey is to give a comprehensive presentation of this angle on structural graph theory. We first give a logic-focused overview of classic graph-theoretic concepts, such as treedepth, shrubdepth, treewidth, cliquewidth, twin-width, bounded expansion, and nowhere denseness. Then, we present recent developments related to notions defined purely through transductions, such as monadic stability, monadic dependence, and classes of structurally sparse graphs. |
| title | Graph classes through the lens of logic |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms Logic in Computer Science |
| url | https://arxiv.org/abs/2501.04166 |