First-order transducibility among classes of sparse graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908373483520000 |
|---|---|
| author | Gajarský, Jakub Gładkowski, Jeremi Jedelský, Jan Pilipczuk, Michał Toruńczyk, Szymon |
| author_facet | Gajarský, Jakub Gładkowski, Jeremi Jedelský, Jan Pilipczuk, Michał Toruńczyk, Szymon |
| contents | We prove several negative results about first-order transducibility for classes of sparse graphs:
- for every $t \in \mathbb{N}$, the class of graphs of treewidth at most $t+1$ is not transducible from the class of graphs of treewidth at most $t$;
- for every $t \in \mathbb{N}$, the class of graphs with Hadwiger number at most $t+2$ is not transducible from the class of graphs with Hadwiger number at most $t$; and
- the class of graphs of treewidth at most $4$ is not transducible from the class of planar graphs.
These results are obtained by combining the known upper and lower bounds on the weak coloring numbers of the considered graph classes with the following two new observations:
- If a weakly sparse graph class $\mathscr D$ is transducible from a class $\mathscr C$ of bounded expansion, then for some $k \in \mathbb{N}$, every graph $G \in \mathscr D$ is a $k$-congested depth-$k$ minor of a graph $H^\circ$ obtained from some $H\in \mathscr C$ by adding a universal vertex.
- The operations of adding a universal vertex and of taking $k$-congested depth-$k$ minors, for a fixed $k$, preserve the degree of the distance-$d$ weak coloring number of a graph class, understood as a polynomial in $d$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_15655 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | First-order transducibility among classes of sparse graphs Gajarský, Jakub Gładkowski, Jeremi Jedelský, Jan Pilipczuk, Michał Toruńczyk, Szymon Logic in Computer Science Discrete Mathematics Combinatorics We prove several negative results about first-order transducibility for classes of sparse graphs: - for every $t \in \mathbb{N}$, the class of graphs of treewidth at most $t+1$ is not transducible from the class of graphs of treewidth at most $t$; - for every $t \in \mathbb{N}$, the class of graphs with Hadwiger number at most $t+2$ is not transducible from the class of graphs with Hadwiger number at most $t$; and - the class of graphs of treewidth at most $4$ is not transducible from the class of planar graphs. These results are obtained by combining the known upper and lower bounds on the weak coloring numbers of the considered graph classes with the following two new observations: - If a weakly sparse graph class $\mathscr D$ is transducible from a class $\mathscr C$ of bounded expansion, then for some $k \in \mathbb{N}$, every graph $G \in \mathscr D$ is a $k$-congested depth-$k$ minor of a graph $H^\circ$ obtained from some $H\in \mathscr C$ by adding a universal vertex. - The operations of adding a universal vertex and of taking $k$-congested depth-$k$ minors, for a fixed $k$, preserve the degree of the distance-$d$ weak coloring number of a graph class, understood as a polynomial in $d$. |
| title | First-order transducibility among classes of sparse graphs |
| topic | Logic in Computer Science Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2505.15655 |