Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2501.18326 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916789448867840 |
|---|---|
| author | Hliněný, Petr Jedelský, Jan |
| author_facet | Hliněný, Petr Jedelský, Jan |
| contents | In a quest to thoroughly understand the first-order transduction hierarchy of hereditary graph classes, some questions in particular stand out; such as, what properties hold for graph classes that are first-order transductions of planar graphs (and of similar classes)? When addressing this (so-far wide open) question, we turn to the concept of a product structure - being a subgraph of the strong product of a path and a graph of bounded tree-width, introduced by Dujmovic et al. [JACM 2020]. Namely, we prove that any graph class which is a first-order transduction of a class admitting such product structure, up to perturbations also meets a structural description generalizing the concept of a product structure in a dense hereditary way - the latter concept being introduced just recently by Hlineny and Jedelsky under the name of H-clique-width [MFCS 2024]. Using this characterization, we show that the class of the 3D grids, as well as a class of certain modifications of 2D grids, are not first-order transducible from classes admitting a product structure, and in particular not from the class of planar graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_18326 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Transductions of Graph Classes Admitting Product Structure Hliněný, Petr Jedelský, Jan Logic in Computer Science Combinatorics In a quest to thoroughly understand the first-order transduction hierarchy of hereditary graph classes, some questions in particular stand out; such as, what properties hold for graph classes that are first-order transductions of planar graphs (and of similar classes)? When addressing this (so-far wide open) question, we turn to the concept of a product structure - being a subgraph of the strong product of a path and a graph of bounded tree-width, introduced by Dujmovic et al. [JACM 2020]. Namely, we prove that any graph class which is a first-order transduction of a class admitting such product structure, up to perturbations also meets a structural description generalizing the concept of a product structure in a dense hereditary way - the latter concept being introduced just recently by Hlineny and Jedelsky under the name of H-clique-width [MFCS 2024]. Using this characterization, we show that the class of the 3D grids, as well as a class of certain modifications of 2D grids, are not first-order transducible from classes admitting a product structure, and in particular not from the class of planar graphs. |
| title | Transductions of Graph Classes Admitting Product Structure |
| topic | Logic in Computer Science Combinatorics |
| url | https://arxiv.org/abs/2501.18326 |