2 papers
cs.DM2024
Monotonicity of the cops and robber game for bounded depth treewidth
Isolde Adler, Eva Fluck
We study a variation of the cops and robber game characterising treewidth, where in each play at most q cops can be placed in order to catch the robber, where q is a parameter of t…
cs.LO2023
On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing
Isolde Adler, Noleen Köhler, Pan Peng
We study property testing of properties that are definable in first-order logic (FO) in the bounded-degree graph and relational structure models. We show that any FO property that…