The first-order-transduction characterization of bounded merge-width

For a graph class C\mathcal{C}, say that it has bounded merge-width when its merge-width is bounded by a constant. A first-order transduction is an interpretation of graphs from structures using first-order formulas, and a graph class has linear neighbourhood complexity when the number of distinct neighbourhoods induced on every pp-element vertex set is O(p)O(p). First-order-transduction characterization of bounded merge-width. A class C\mathcal{C} has bounded merge-width if and only if every first-order transduction of C\mathcal{C} has linear neighbourhood complexity. This proposes a dense-graph analogue of the characterization of bounded expansion by linear neighbourhood complexity, replacing ordinary neighbourhoods by first-order transductions. The paper establishes linear neighbourhood complexity for bounded merge-width at radius 22, but the stated if-and-only-if characterization is not proved in the supplied text.

Sources & referencesView supporting material

Primary source

Marthe Bonamy and Colin Geniet, “χ-Boundedness and Neighbourhood Complexity of Bounded Merge-Width Graphs”, arXiv:2504.08266 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.