Pith. sign in

REVIEW 5 cited by

On first-order transductions of classes of graphs

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2208.14412 v8 pith:U6E42RHZ submitted 2022-08-30 math.CO cs.DMcs.LOmath.LO

Samuel Braunfeld , Jaroslav Nešetřil , Patrice Ossona de Mendez , Sebastian Siebertz This is my paper · ORCID
classification math.COcs.DMcs.LOmath.LO
keywords classesquasi-orderfirst-ordergraphtransductionsaspectslogicother
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

We study various aspects of the first-order transduction quasi-order on graph classes, which provides a way of measuring the relative complexity of graph classes based on whether one can encode the other using a formula of first-order (FO) logic. In contrast with the conjectured simplicity of the transduction quasi-order for monadic second-order logic, the FO-transduction quasi-order is very complex, and many standard properties from structural graph theory and model theory naturally appear in it. We prove a local normal form for transductions among other general results and constructions, which we illustrate via several examples and via the characterizations of the transductions of some simple classes. We then turn to various aspects of the quasi-order, including the (non-)existence of minimum and maximum classes for certain properties, the strictness of the pathwidth hierarchy, the fact that the quasi-order is not a lattice, and the role of weakly sparse classes in the quasi-order.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 5 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. First-order transducibility among classes of sparse graphs

    cs.LO 2025-05 accept novelty 8.0 of 10

    Treewidth t+1 graphs are not first-order transducible from treewidth t graphs, with analogous separations for Hadwiger number and for treewidth 4 graphs from planar graphs.

  2. k-Planar and Fan-Crossing Drawings and Transductions of Embeddable Graphs

    cs.CG 2025-06 conditional novelty 7.0 of 10

    Sparse graph classes are first-order transducible from graphs on a fixed surface if and only if they admit a new type of bounded fan-crossing drawing on that surface.

  3. Transductions of Graph Classes Admitting Product Structure

    cs.LO 2025-01 accept novelty 7.0 of 10

    Transductions of product-structured classes are, up to perturbation, exactly bounded path-power clique-width classes, which excludes 3D grids and pinned grid families.

  4. Boolean combinations of graphs

    math.CO 2024-12 conditional novelty 7.0 of 10

    Boolean combinations of graphs give new characterizations of subexponential, subfactorial and structurally bounded degree graph classes, and yield new polynomial and linear chi-boundedness results.

  5. Graph classes through the lens of logic

    math.CO 2025-01 accept novelty 2.0 of 10

    A survey presenting first-order transductions as a unifying lens for graph classes, connecting sparsity, twin-width, and monadic stability and dependence.

Pith tools