The first-order-transduction characterization of bounded merge-width
The first-order-transduction characterization of bounded merge-width
For a graph class , 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 -element vertex set is . First-order-transduction characterization of bounded merge-width. A class has bounded merge-width if and only if every first-order transduction of 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 , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.